Team Dai-Gurren is getting ready to launch a raid on an Anti-Spiral dungeon. The dungeon has ~N~ ~(2 \le N \le 100\,000)~ rooms and ~M~ ~(1 \le M \le 200\,000)~ bidirectional corridors. Room ~1~ is the entrance. All raid members start at the entrance and they must arrive at the boss room, which is one of the rooms (exactly which is unknown to team Dai-Gurren). A single corridor contains some Anti-Spirals and connects two rooms together. No corridor connects a room to itself, and two rooms have at most one corridor between them. It is guaranteed that you can follow a sequence of corridors from one room to any other room.

Some Anti-Spiral drones are patrolling the dungeon. Each drone moves along a sequence of ~k~ distinct rooms ~r_1\ r_2\ \ldots\ r_k~ such that there is a corridor between every two adjacent rooms in the sequence and there is also a corridor between ~r_1~ and ~r_k~. Additionally, no corridor is repeated twice or more in the sequence. For every subset of rooms that belong to such a sequence, there is exactly one drone patrolling rooms in that subset. A curious fact about this dungeon is that no matter how fast or slow each individual drone moves, if two different drones can meet each other, then they will only ever meet each other in exactly one room. Different pairs of drones may have different meeting rooms. Since the members of Team Dai-Gurren are powerful beyond belief, drones pose no problem at all and can be safely ignored for the rest of the mission.

During the raid, no two raid members may travel through the same corridor, because the raid leader wants members to scout out the dungeon while travelling. However, two or more raid members are allowed to travel through the same room. Raid members are lazy, so they want to encounter the least total number of Anti-Spirals as possible on their way from the entrance to the boss room. Given these constraints, what is the maximum size of a raid party, and what is the minimum total number of Anti-Spirals the raid members will encounter on their way to the boss room? Answer this question for every potential raid plan considering that the boss room is a room from ~2~ to ~N~.

Input Specification

The first line of input will contain ~N~ and ~M~, separated by a single space.

The next ~M~ lines will each be in the form ~u\ v\ w~, describing a two-way corridor from ~u~ to ~v~ with ~w~ Anti-Spirals in it ~(1 \le u, v \le N, u \neq v, 1 \le w \le 100\,000)~.

It is guaranteed that the input will conform to the additional constraints mentioned earlier.

Output Specification

For each room ~i~ from ~2~ to ~N~, output a single line with two integers separated by a space.

The first number should be the maximum size of the raid party if room ~i~ is the boss room.

The second number should be the minimum total number of Anti-Spirals all the raid members in a party of maximum size encounter if room ~i~ is the boss room.

It is guaranteed that neither number will exceed ~2^{63}-1~. You should consider each raid plans independent of other raid plans (i.e. which corridors were used in one raid plan does not affect which corridors can be used in the next raid plan).

Sample Input

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

Sample Output

2 5
2 5
1 3

Diagram for Sample Input