Recently Syrjälä's network collapsed, and now it's being rebuilt. Uolevi wants to know the earliest moment when he can play an online game. Given information about when the connections between computers are built, and the times required for a signal to go through particular connections, Uolevi wants to know the earliest moment when his ping (the lowest possible time required for a signal to go from Uolevi's computer to the game server through connections) is low enough.

The computers are numbered 1, 2, \ldots, n. Uolevi's computer is number 1 and the game server is number n. Initially there are no connections between the computers.

Input

The first line of input contains three integers, n, q and p, the number of computers, the number of updates and the highest ping which is low enough. Then follows q lines containing three integers each, u_i, v_i and d_i meaning that at time i a bidirectional connection between computers u_i and v_i is built. d_i is time required for a signal to go through the connection.

Output

Output a single integer, the lowest i such that after first i updates Uolevi can play the game with low enough ping. If Uolevi can never play the game with low enough ping, output QAQ.

Constraints

• 2 \le n \le 10^5
• 0 \le q \le 10^5
• 1 \le p \le 10^9
• 1 \le u_i, v_i \le n
• 1 \le d_i \le 10^9

Examples

Input:

4 5 4
1 4 5
2 1 1
4 3 2
1 3 2
2 4 1

Output:

4

Input:

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

Output:

QAQ