A set of laboratory mice is being trained to escape a maze. The maze is made up of cells, and each cell is connected to some other cells. However, there are obstacles in the passage between cells and therefore there is a time penalty to overcome the passage Also, some passages allow mice to go one-way, but not the other way round.
Suppose that all mice are now trained and, when placed in an arbitrary cell in the maze, take a path that leads them to the exit cell in minimum time.
We are going to conduct the following experiment: a mouse is placed in each cell of the maze and a count-down timer is started. When the timer stops we count the number of mice out of the maze.
Write a program that, given a description of the maze and the time limit, predicts the number of mice that will exit the maze. Assume that there are no bottlenecks is the maze, i.e. that all cells have room for an arbitrary number of mice.

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The maze cells are numbered 1, 2, ..., N, where N is the total number of cells. You can assume that \( N \leq 100\).
The first three input lines contain N, the number of cells in the maze, E, the number of the exit cell, and the starting value T for the count-down timer (in some arbitrary time unit).
The fourth line contains the number M of connections in the maze, and is followed by M lines, each specifying a connection with three integer numbers: two cell numbers a and b (in the range 1, 2, ..., N) and the number of time units it takes to travel from a to b.
Notice that each connection is one-way, i.e., the mice can't travel from b to a unless there is another line specifying that passage. Notice also that the time required to travel in each direction might be different.

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of a single line with the number of mice that reached the exit cell E in at most T time units.

Sample Input
1

4
2
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

Sample Output
3

#include<stdio.h>
#include<stdlib.h>
#define V 101

typedef int element;
struct cell { 
	element data; 
	int priority;
	struct cell *next; 
};
 

typedef  struct { 
	struct cell *front; 
} queue;

 

queue CreateQueue()
{
	queue q;
	q.front = NULL;
	return q;
}

int isEmptyQueue(queue q)
{
	return q.front == NULL;
}

int EnQueue(queue *q, element e, int priority)
{
	struct cell *temp, *href;
	temp = (struct cell *) malloc(sizeof(struct cell));
	if (!temp) return 0;
	temp->data = e;
	temp->priority = priority;
	if (q->front == NULL || priority < q->front->priority) {/*Queue is empty or item to be added has priority more than first item*/
		temp->next = q->front;
		q->front = temp;
	}
	else
	{
		href = q->front;
		while (href->next != NULL && href->next->priority <= priority)
			href = href->next;
		temp->next = href->next;
		href->next = temp;
	}

	return 1;
}

int DeQueue(queue *q)
{
	struct cell *temp;
	if (isEmptyQueue(*q)) return 0;
	temp = q->front;
	q->front = q->front->next;
	free(temp);
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.front->data;
	return 1;
}

 

void display_queue(queue tmp)
{
	struct cell *temp = tmp.front;

	if (temp == NULL)
		printf("Queue is empty\n");
	else
	{
		printf("Queue is :\n");
		printf("Item\n");
		while (temp != NULL)
		{
			printf("%5d         %5d\n\n", temp->priority, temp->data);
			temp = temp->next;
		}
	}
}
void delete_head(struct cell **nodeRef)
{
	struct cell *p;
	p = *nodeRef;
	*nodeRef = (*nodeRef)->next;
	free(p);
}

// delete a given element (recursive)
int delete_value(struct cell **nodeRef, element e)
{
	if (*nodeRef == NULL)
		return 0;
	if ((*nodeRef)->data == e)
	{
		delete_head(nodeRef);
		return 1;
	}
	return delete_value(&((*nodeRef)->next), e);
}


void recursive_ordered_insert(struct cell **node, element value, int priority)
{
	struct cell *temp;
	if ((*node == NULL) || !((*node)->priority < priority))
	{
		temp = *node;
		*node = (struct cell *) malloc(sizeof(struct cell));
		if (!*node) return ;
		(*node)->data = value;
		(*node)->priority = priority;
		(*node)->next = temp;
		return;
	}

	 recursive_ordered_insert(&((*node)->next), value, priority);

}


void update_priority(queue *q, element data, int priority) {
	if (delete_value(&(q->front), data) == 1)
		recursive_ordered_insert(&(q->front), data, priority);
}

 

void test() {
	int N, D, TLE, M;
	int i;
	int X, Y ,W;
	int distance[V];
	int **Adj;
	int v;
	int ans;
	int dist;
	queue q;
	

	scanf("%d %d %d %d", &N, &D, &TLE, &M );

	 
 	Adj = (int **)malloc((N+1) * sizeof(int*));
	for (i = 1; i <= N; i++)
	{
		Adj[i] = (int *)malloc((N+1) * sizeof(int));
		distance[i] = -1;
	}


	for(i=0;i<M;i++)
	{
		scanf("%d %d %d", &X, &Y, &W);
		Adj[X][Y] = W;
	}

	q = CreateQueue();
	EnQueue(&q, D, 0);
	distance[D] = 0;
	while(Front(q, &v)) 
	{
		DeQueue(&q);
		for (i = 1; i<=N; i++) 
			if (Adj[v][i] != 0) {
				dist = distance[v]+ Adj[v][i];
				if (distance[i] == -1) {
					distance[i] = dist;
					EnQueue(&q, i, dist);
				}
				else
					if (distance[i] > dist) {
						distance[i] = dist;
						update_priority(&q, i, dist);
					}

			}
	}
	
	ans=0;
	for(i=1;i<=N;i++)

		if(distance[i]<=TLE)
			ans++;
	printf("%d\n",ans);	
	
}


int main()
{
	int tests;

	scanf("%d", &tests);

	while (tests--)
	{
		test();
		if(tests)
			printf("\n");
	}
	return 0;
}