Сізде \(n\) төбесі және \(m\) қыры бар салмақтаған бағытталмаған граф бар, ол \(u_i\), \(v_i\) және \(w_i\) жиымдары арқылы берілген. Содан кейін \(m\) төбесі бар жаңа граф құрылады. Бастапқы графта \((u_i, v_i)\) және \((u_j, v_j)\) қырларында ортақ төбе болса, жаңа графта \(i\)-ші төбемен \(j\)-ші төбе арасында салмағы \(w_i \cdot w_j\) болатын қыр болады. Сіздің тапсырмаңыз – бұл жаңа графтағы \(1\) төбесінен барлық \(v\) (\(1\le v \le m\)) төбелеріне қысқаша жолдардың ұзындықтарын табу.

Input

Бірінші жолда \(n\) және \(m\) (\(2 \le n \le 2 \times 10^5\), \(0 \le m \le 2 \times 10^5\)) берілген – бастапқы графтағы төбелер мен қырлардың саны.

Келесі \(m\) жолда үш бүтін саннан беріледі: \(u_i\), \(v_i\) және \(w_i\) (\(1 \le u_i, v_i \le n\), \(u_i \ne v_i\), \(1 \le w_i \le 10^6\)), қырдың төбелері мен ұзындығы.

Output

Әрбір \(v\) \((1 \le v \le m)\) төбесі үшін \(1\) төбесінен \(v\) төбесіне дейінгі қысқаша жолдың ұзындығын шығарыңыз. Егер \(v\) төбесіне ешқандай жол болмаса, \(-1\) санын шығарыңыз.

Sample Input 1

5 5
1 2 3
2 3 5
2 4 10
3 4 5
4 5 6

Sample Output 1

0 15 30 40 70

Sample Input 2

5 6
1 2 10
2 1 1
1 2 100
1 3 30
1 3 50
4 5 1000

Sample Output 2

0 10 110 40 60 -1