Dat je neusmeren tezinski graf sa A cvorova i M grana. Cvorovi grafa su oznaceni brojevima od 1 do N. Svaka grana povezuje dva razlicita cvora i ima pozitivnu tezinu. Treba odrediti najkracu kruznu putanju koja sadrzi cvorove 1 i N i gde se svaki cvor pojavljuje najvise jedanput. Kruzna putanja je put od cvora 1 do N potencijalno preko nekih cvorova i put od cvora N do cvora 1 potencijalno preko nekih cvorova.

INPUT:
Podaci se ucitavaju sa standardnog ulaza. U prvom redu se nalaze brojevi N i M (2 <= N <= 1000, 1 <= M <= 10000), koji predstavlja broj cvorova i grana u grafu. U svakom od sledecih M redova nalaze se tri prirodna broja X , Y i W razdvojeni razmakom (1 <= X , Y <= N, 1 <= W <= 100000), koji oznacavaju da postoji neusmerena grana tezine W koja spaja cvorove X i Y.

OUTPUT:
Na standardnom izlazu u jednoj liniji stampati duzinu najkrace kruzne putanje koja sadrzi cvorove 1 i N. Garantuje se da postojanje barem jedanog takvog ciklusa.

Input:


Output:

Obrazlozenje primera: Ciklus 1 -> 2 -> 4 -> 3 -> 1 je trazeno resenje sa ukupnom tezinom 1 + 2 + 1 + 2 = 6.