Hằng ngày Bi được Ba chở đi học từ nhà đến trường, đi qua nhiều con đường khác nhau. Vì là công việc quen thuộc nên hầu như trở thành thói quen, Bi quan sát và đo được chính xác thời gian đi qua của mỗi con đường và dễ dàng tính chính xác được tổng thời gian đi từ nhà đến trường (Ba Bi có học toán đồ thị nên sử dụng chính xác thuật toán đi sao cho có thời gian nhỏ nhất). Tuy nhiên, do đi vào những giờ vàng nên thường xuyên xảy ra nạn kẹt xe, mỗi lần kẹt xe trên một đoạn đường nào đó thì thời gian tăng lên gấp đôi trên đoạn đường đó. Không tính trường hợp kẹt xe ở điểm giao nhau. Đường đi trong thành phố đều hai chiều và không có nhiều hơn một đường đi nối giữa hai địa điểm.

Nhà Bi ở địa điểm ~1~, Trường ở địa điểm ~n~. Hãy viết chương trình tính giúp Bi xem thời gian bị trễ hơn so với trường hợp không kẹt xe.

Input

Dòng thứ nhất chứa số hai số nguyên dương ~n, m~ thỏa ~1 \le n \le 100, 1 \le m \le 10000~. ~n~ là số điểm giao của các con đường và ~m~ là số con đường.

~m~ dòng tiếp theo chứa bộ ba phần tử ~v_i, v_j, t_i~ thỏa ~1 \le v_i \neq v_j \le n; 1 \le t_i \le 10^6~ biểu diễn thời gian đi từ địa điểm ~v_i~ đến ~v_j~ là ~t_i~.

Output

In ra thời gian trễ cần tìm.

Samples

Sample Input 1

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

Sample Output 1

2