Description

Mr. R and his friends plan to play a racing game, but they were tricked by the experienced driver mocania into going to Mount Akina.

On Mount Akina, there are $n$ nodes and $m$ edges. Mr. R and his friends need to start from node $1$ and drive to node $n$. Each edge has an initial direction. The experienced driver mocania got the map of Mount Akina, but does not know how long each road is. Obviously, for fairness in the racing game, every path from $1$ to $n$ should have the same total length. mocania thinks: “I will just assign each edge a length from $1...9$. Anyway, the silly Mr. R will not be able to tell.”

However, mocania is not very good at math and does not know how to assign lengths to the edges, so he comes to ask you, an OI expert, for help.

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain two integers $u, v$, indicating a directed edge from $u$ to $v$.

Output Format

If there is no solution, or if there is no path from $1$ to $n$, output $-1$.

If there is a solution, output two numbers $n, m$ on the first line, the same as in the input file.

Then output $m$ lines. Each line contains three integers $u, v, w$, meaning the length of the edge from $u$ to $v$ is set to $w$, where $w$ is an integer in $1\sim 9$. The order of all edges must be the same as in the problem statement.

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10

10 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 10 9

Hint

Constraints

This problem uses Special Judge and Subtask.

Subtask #1 ($30$ points): $n \leq 10$, $m \leq 20$.
Subtask #2 ($30$ points): $n \leq 100$, $m \leq 200$.
Subtask #3 ($40$ points): $n \leq 1000$, $m \leq 2000$.

It is guaranteed that there are no multiple edges or self-loops in the testdata.

Translated by ChatGPT 5