Problem Description

Today, the squirrel's job is to transport acorns from one tree to another.
The forest where the squirrel lives has a total of $ N $ trees, each labeled with an integer from $ 1 $ to $ N $. There are also $ M $ branches that allow travel between trees, and the $ i $-th branch ($1 \leq i \leq M$) allows bidirectional travel between tree $ A_i $ and tree $ B_i $.
Each branch has a gap of size $ C_i $ that the squirrel must jump across. The squirrel can easily jump gaps of the same size, but jumping gaps of different sizes while carrying acorns is tiring, so the squirrel decided to take a break before jumping a gap of a different size from the previous one. However, the first jump does not require a break.

The squirrel starts at tree $ 1 $ with acorns and needs to transport them to tree $ N $ via the route with the fewest breaks.
Iroha-chan, the spirit of the forest, wants to place $ K $ snacks on the trees where the squirrel takes breaks and on the goal tree.
How many snacks does Iroha-chan need to prepare?

Input Format

Given in the following format:

$N\ M\ K$ $A_1\ B_1\ C_1$ $\vdots$ $A_M\ B_M\ C_M$

Output Format

Output the minimum number of snacks needed. If the squirrel cannot reach tree $ N $, output -1. Otherwise, since all squirrels take the same route, output $+ 1) \times K$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1

Sample Input #2

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

Sample Output #2

4

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq K \leq 10^4$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• For $i \neq j$, $(A_i, B_i, C_i) \neq (A_j, B_j, C_j)$
• $1 \leq C_i \leq 10^5$

Explanation

Explanation

Sample Explanation 1

- - - - - - ### Input Example 2 5 5 2 1 2 1 2 3 1 2 4 2 3 4 3 4 5 2 ### Output Example 2 4 ### Explanation Explanation

见题面 Input 部分

见题面 Output 部分