int _tmain(int argc, _TCHAR* argv[])
{
	int speed, cost;
	float road_clearance;
	std::string s;
	TQueue<Cars> q;
	int choice = 0;
	Cars *item;
	std::cout << "Hello, here are possbile actions: " << std::endl;
	std::cout << "1: Push item (Press a).  Enter\n\t1. Jeep. Then enter price and road clearance\n\t2. Sedan. Then enter price and speed\n\t3. Hatchback. Then enter price and speed" << std::endl;
	std::cout << "2: Pop item (Press p)" << std::endl;
	std::cout << "3: Search (Press s).  Enter\n\t1. Jeep. Then enter price and road clearance\n\t2. Sedan. Then enter price and speed\n\t3. Hatchback. Then enter price and speed" << std::endl;;
	std::cout << "4: Remove item (Press r). Enter\n\t1. Jeep. Then enter price and road clearance\n\t2. Sedan. Then enter price and speed\n\t3. Hatchback. Then enter price and speed" << std::endl;
	std::cout << "5: Destroy all container (Press d)" << std::endl;
	std::cout << "6: Output  all container items (Press o)" << std::endl;
	std::cout << "6: Quit (Press q)" << std::endl;
	
	while ((choice = getchar()) != 'q') {
		fflush(stdin);
		switch (choice) {
			std::cout << choice << std::endl;
		case 'a':
			if ((choice = getchar()) == '1') {
				std::cin >> cost >> road_clearance;
				Jeep jeep(cost, road_clearance);
				q.PushBack(jeep);
			}
			else if (choice == '2') {
				std::cin >> cost >> speed;
				q.PushBack(Sedan(cost, speed));
			}

static double least(void* v) {
    TQueue* q = (TQueue*)v;
    TQItem* i = q->least();
    double x = -1e9;
    if (i) {
        x = i->t_;
    }
    return x;
}

static double find(void* v) {
    TQueue* q = (TQueue*)v;
    TQItem* i = q->find(*getarg(1));
    double x = -1e9;
    if (i) {
        x = i->t_;
        q->remove(i);
    }
    return x;
}

void FogWorker::FloodFill(int32 x, int32 y)
{
    if(x < 0 || x >= TextureSize || y < 0 || y >= TextureSize)
    {
        return;
    }

    // Wikipedia
    // Flood-fill (node, target-color, replacement-color):
    // 1. If target - color is equal to replacement - color, return.
    // 2. If color of node is not equal to target - color, return.
    if(FMath::IsNearlyEqual(UnfoggedData[x + y * TextureSize], 1.0f))
    {
        return;
    }
    // 3. Set Q to the empty queue.
    TQueue<FIntVector> Q;
    // 4. Add node to Q.
    Q.Enqueue(FIntVector(x, y, 0));

    FIntVector N;
    // 5. For each element N of Q :
    while(Q.Dequeue(N))
    {
        // 6. Set w and e equal to N.
        auto w = N, e = N;
        // 7. Move w to the west until the color of the node to the west of w no longer matches target - color.
        while(w.X - 1 > 0 && !FMath::IsNearlyEqual(UnfoggedData[w.X - 1 + w.Y * TextureSize], 1.0f))
        {
            w.X--;
        }
        // 8. Move e to the east until the color of the node to the east of e no longer matches target - color.
        while(e.X + 1 < TextureSize && !FMath::IsNearlyEqual(UnfoggedData[e.X + 1 + e.Y * TextureSize], 1.0f))
        {
            e.X++;
        }
        // 9. For each node n between w and e :
        for(auto i = w.X; i <= e.X; ++i)
        {
            FIntVector n(i, N.Y, 0);
            // 10. Set the color of n to replacement - color.
            UnfoggedData[n.X + n.Y * TextureSize] = 1.0f;
            // 11. If the color of the node to the north of n is target - color, add that node to Q.
            if(n.Y + 1 < TextureSize && !FMath::IsNearlyEqual(UnfoggedData[n.X + (n.Y + 1) * TextureSize], 1.0f))
                Q.Enqueue(FIntVector(n.X, n.Y + 1, 0));
            // 12. If the color of the node to the south of n is target - color, add that node to Q.
            if(n.Y - 1 > 0 && !FMath::IsNearlyEqual(UnfoggedData[n.X + (n.Y - 1) * TextureSize], 1.0f))
            {
                Q.Enqueue(FIntVector(n.X, n.Y - 1, 0));
            }
        }
        // 13. Continue looping until Q is exhausted.
    }
    // 14. Return.
}

  void OutputQueue(TQueue queue)
  {
    typename TQueue::key_map propertyMap = queue.keys();

    // Read out the queue, saving the objects in the order they were in the queue
    while(!queue.empty())
    {
      typename TQueue::value_type queuedObject = queue.top();
      std::cout << "queuedObject: " << queuedObject << " ";
      typename boost::property_traits<typename TQueue::key_map>::value_type value = get(propertyMap, queuedObject);
      std::cout << " value: " << value << std::endl;
      queue.pop();
    }
  }

bool FAppEventManager::WaitForEventInQueue(EAppEventState InState, double TimeoutSeconds)
{
	bool FoundEvent = false;
	double StopTime = FPlatformTime::Seconds() + TimeoutSeconds;

	TQueue<FAppEventData, EQueueMode::Spsc> HoldingQueue;
	while (!FoundEvent)
	{
		int rc = pthread_mutex_lock(&QueueMutex);
		check(rc == 0);

		// Copy the existing queue (and check for our event)
		while (!Queue.IsEmpty())
		{
			FAppEventData OutData;
			Queue.Dequeue(OutData);

			if (OutData.State == InState)
				FoundEvent = true;

			HoldingQueue.Enqueue(OutData);
		}

		if (FoundEvent)
			break;

		// Time expired?
		if (FPlatformTime::Seconds() > StopTime)
			break;

		// Unlock for new events and wait a bit before trying again
		rc = pthread_mutex_unlock(&QueueMutex);
		check(rc == 0);
		FPlatformProcess::Sleep(0.01f);
	}

	// Add events back to queue from holding
	while (!HoldingQueue.IsEmpty())
	{
		FAppEventData OutData;
		HoldingQueue.Dequeue(OutData);
		Queue.Enqueue(OutData);
	}

	int rc = pthread_mutex_unlock(&QueueMutex);
	check(rc == 0);

	return FoundEvent;
}

    bool do_command(char c, TQueue &queue)
    {
        bool continue_input = true;
        TQueue::entry_type x;

        switch (c)
        {
        case 'r':
        case 'R':
            if (TQueue::underflow == queue.retrieve(x))
            {
                std::cout << "Queue is empty!" << std::endl;
            }
            else
            {
                std::cout << std::endl << "The first entry is : " << x << std::endl;
            }
            break;
        case 's':
        case 'S':
            break;
        case 'a':
        case 'A':
            break;
        case '#':
            break;
        case 'q':
        case 'Q':
            return false;
        default:
            std::cout << "Command is not implemented!" << std::endl;
        }

        return continue_input;
    }

void AVL::breadFirstPrint(){
  TQueue<Node*> q;
  if(root_){
    q.enqueue(root_);
    while(!q.isEmpty()){
      Node* curr=q.front();
      q.dequeue();
      if(curr->left_)
        q.enqueue(curr->left_);
      if(curr->right_)
        q.enqueue(curr->right_);
      cout << curr->data_ << endl;
      
    }
  }
}

void TwoThreeTree::levelOrder() {
    if (root == NULL) return;

    // Use a tree to do levelOrder Traversal
    TQueue queue;
    queue.push(root);
    root->level = 0;

    cout << "Level Order Traversal:\n";

    int currentLevel = 0;
    while (!queue.isEmpty()) {
        const TNode *t = queue.top();
        
        if (t->level != currentLevel) {
            cout << endl;
            currentLevel = t->level;
        }
        
        // push t's children on queue, set their level nubmer
        t->print();
        if (!t->isLeaf) {
            int nextLevel = t->level + 1;
            t->left->level = nextLevel;
            queue.push(t->left);

            t->middle->level = nextLevel;
            queue.push(t->middle);

            if (t->rlow != -1) {
                t->right->level = nextLevel;
                queue.push(t->right);
            }
        }

        queue.pop();
    }
    cout << endl << endl;
}

void DFS(const TGraph& g, int v, TLine* result) {
	result->resize(g.size());
	fill(result->begin(), result->end(), -1);
	TQueue q;
	(*result)[v] = 0;
	q.push(v);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < g[now].size(); ++i) {
			int next = g[now][i];
			if (-1 == (*result)[next]) {
				(*result)[next] = (*result)[now] + 1;
				q.push(next);
			}
		}
	}
}

static double print(void* v) {
    TQueue* q = (TQueue*)v;
    q->print();
    return 1.;
}

void sim()
{
	int j = 0;
	int tickskip = 0, proctime = 0, taskskip = 0;
	int tick;
	int critT, critP;
	TQueue queue;

	printf("??????? ??????????? ???????? ?????\n");
	critT = input(DIAP);
	printf("??????? ??????????? ???????? ??????????\n");
	critP = input(DIAP);

	printf("??????? ?????????? ??????\n");
	tick = input(9000);
	if (tick < 20)
	{
		for (int i = 0; i < tick; i++)
		{
			if (TaskRand(critT))
			{
				if (!queue.IsFull())
				{
					queue.Put(1);
					printf("????????? ??????\n");
				}
				else
				{
					taskskip++;
					printf("?????? ?????????\n");
				}
			}
			if (proctime != 0)
			{
				printf("????????? ???????????? ??????\n");
				if (ProcRand(critP))
				{
					proctime = 0;
					printf("?????? ??????????\n");
				}
				else
				{
					proctime++;
					printf("?????? ??????????????\n");
				}
			}
			else if (!queue.IsEmpty())
			{
				printf("????????? ?????? ??????\n");
				queue.Push();
				if (ProcRand(critP))
				{
					printf("?????? ??????????\n");
				}
				else
				{
					proctime++;
					printf("?????? ??????????????\n");
				}
			}
			else
			{
				tickskip++;
				printf("????????? ???????????\n");
			}
		}
		while (!queue.IsEmpty())
		{
			queue.Push();
			j++;
		}
	}
	else
	{
		for (int i = 0; i < tick; i++)
		{
			if (TaskRand(critT))
			{
				if (!queue.IsFull())
				{
					queue.Put(1);
				}
				else
				{
					taskskip++;
				}
			}
			if (proctime != 0)
			{
				if (ProcRand(critP))
				{
					proctime = 0;
				}
				else
				{
					proctime++;
				}
			}
			else if (!queue.IsEmpty())
			{
//.........这里部分代码省略.........

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	int n = ReadInt();
	int m = ReadInt();

	int s = ReadInt() - 1;
	int f = ReadInt() - 1;

	TGraph g(n);
	for (int i = 0; i < m; ++i) {
		int begin = ReadInt() - 1;
		int end = ReadInt() - 1;
		int cost = ReadInt();

        double p = 1.0 - static_cast<double>(cost) / 100.0;
		g[begin].push_back( TNode(end, p) );
		g[end].push_back( TNode(begin, p) );
	}

    /*
    for (int i = 0; i < n; ++i) {
        shuffle(g[i].begin(), g[i].end(), default_random_engine());
    }
    */

    const TCost INF(n + 1000, -10.0);
    TCosts costs(n, INF);
    TIntegers parent(n, -1);
    parent[s] = -2;

    TQueue q;
    {
        const TCost cost(0, 1.0);
        q.push(s);
        costs[s] = cost;
    }

    while (!q.empty()) {
        const int now = q.front();
        q.pop();
        if (now == f) {
            break;
        }
        const TCost& nowCost = costs[now];
        for (TNodes::const_iterator toNode = g[now].begin(); toNode != g[now].end(); ++toNode) {
            const int next = toNode->_to;
            TCost nextCost(nowCost._iDist + 1, nowCost._fine*toNode->_p);
            if (-1 == parent[next] || ((nowCost._iDist + 1 == costs[next]._iDist) && (nowCost._fine*toNode->_p > costs[next]._fine))) {
                if (-1 == parent[next]) {
                    q.push(next);
                }
                costs[next] = nextCost;
                parent[next] = now;
            }
        }
    }

    TIntegers path;
    int now = f;
    while (-2 != now) {
        path.push_back(now);
        now = parent[now];
    }

    printf("%d %.12lf\n", path.size(), 1.0 - costs[f]._fine);
    for (TIntegers::const_reverse_iterator toPath = path.rbegin(); toPath != path.rend(); ++toPath) {
        printf("%d ", *toPath + 1);
    }
    printf("\n");

	return 0;
}

static double remove(void* v) {
    TQueue* q = (TQueue*)v;
    q->remove(q->find(*getarg(1)));
    return 1.;
}

static double mvleast(void* v) {
    TQueue* q = (TQueue*)v;
    q->move_least(*getarg(1));
    return 1.;
}

static double stats(void* v) {
    TQueue* q = (TQueue*)v;
    q->statistics();
    return 1.;
}

static double insert(void* v) {
    TQueue* q = (TQueue*)v;
    q->insert(*getarg(1), (void*)1);
    return 1.;
}

TInt DZeroCopyLoopbackDevice::RequestDataReceipt()
	{
	iPendingRead = ETrue;
	if(!(iReceiveQueue.IsEmpty() && iSendQueue.IsEmpty()))
		{
		NKern::Lock(); 
		ReceiveDataCallback();
		NKern::Unlock(); 
		}
	return KErrNone;
	}

TInt DZeroCopyLoopbackDevice::RequestDataSend()
	{
	// Push our send buffer in to the queue
	iSendQueue.Push();
	
	// Trigger reception
	NKern::Lock(); 
	SendDataCallback();
	NKern::Unlock(); 
	
	return KErrNone;
	}

DWORD WINAPI LocalThread(LPVOID parms)
{
	try {
		for(int i=0;i<1000;i++)
		{
			printf("put %d\n",i);
			q.Put(i);
			Sleep(10);
		}
	}
	catch(const char * c) 
	{
		printf("EXCEPTION in THREAD: %s, err=%d\n",c,GetLastError());
	}
	return 0;
}