무빙워크

UDP 시티는 $N$개의 건물과 각 건물을 잇는 $M$개의 무빙워크로 이루어져 있다. 각 건물과 무빙워크에는 $1$번부터 차례로 번호가 매겨져 있다. 포닉스는 각 무빙워크의 전원을 끄거나 켤 수 있다. 무빙워크는 전원 상태에 따라 아래와 같이 동작한다.

• $i$번째 무빙워크의 전원이 켜져 있는 경우, $u\_i$번 건물에서 $v\_i$번 건물로의 방향으로만 이동할 수 있다. 이 경우 이동 시간은 $d\_i$이다.
• $i$번째 무빙워크의 전원이 꺼져 있는 경우, $u\_i$번 건물과 $v\_i$번 건물 사이를 방향에 관계없이 이동할 수 있다. 이 경우 이동 시간은 $2d\_i$이다.

포닉스는 현재 $1$번 건물에 있으며, 각 무빙워크의 전원을 적절히 조작해 다른 모든 건물에 대한 최단 도달 시간의 합을 최소화하려 한다. 이때 $1$번 건물에서 도달할 수 없는 건물이 존재해서는 안 된다.

도달할 수 없는 건물이 존재하지 않는 모든 경우에 대해서 모든 건물에 대한 최단 도달 시간의 합의 최솟값과 이때 각 무빙워크의 전원 상태를 구해 보자.

첫째 줄에 건물의 개수 $N$, 무빙워크의 개수 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 300\ 000; 1 \le M \le 500\ 000)$

둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u\_i, v\_i, d\_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 무빙워크의 전원이 켜져 있을 때 $u\_i$번 건물에서 $v\_i$번 건물으로 이동하는 것이 가능하며 $d\_i$의 이동 시간을 가짐을 의미한다. $(1 \le u\_i, v\_i \le N; u\_i \ne v\_i; 1 \le d\_i \le 10^6)$

모든 무빙워크의 전원을 껐을 때, $1$번 건물에서 다른 모든 건물로 도달할 수 있음이 보장되며 서로 다른 무빙워크에 대해 $(u, v)$ 쌍은 서로 다르다.

첫째 줄에 가능한 최단 도달 시간 합의 최솟값을 출력한다.

둘째 줄에는 각 무빙워크의 전원 상태를 나타내는 정수 $P\_1, P\_2, \cdots , P\_M$을 공백으로 구분해 출력한다. $P\_i$는 $i$번째 무빙워크의 전원을 켜야 할 경우 $1$, 꺼야 할 경우 $0$이다. 가능한 전원 상태가 여러 개일 경우 그 중 아무것이나 출력하여라.