CSES - HIIT Open 2016 Practice

## HIIT Open 2016 Practice

 Contest start: 2016-05-19 17:00:00 Contest end: 2016-05-28 9:00:00

Ping

 Time limit: 3.00 s Memory limit: 128 MB

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