Syrjälän tietoverkossa on $n$ konetta, joiden välillä on $m$ yhteyttä. Jokainen yhteys on yksisuuntainen ja sen ylläpito maksaa tietyn verran.

Yksi koneista on warepalvelin, ja on hyvin tärkeää, että siitä on yhteys kaikkiin muihin koneisiin. Muilla yhteyksillä ei ole niin väliä.

Tehtäväsi on valita joukko yhteyksiä niin, että warepalvelimelta on yhteys kaikkiin koneisiin ja yhteyksien kokonaiskustannus on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: koneiden määrä ja yhteyksien määrä. Koneet on numeroitu kokonaisluvuin $1,2,\dots,n$, ja kone $1$ on warepalvelin.

Sitten syötteessä on $m$ riviä, joista jokaisella on kolme kokonaislukua $a$, $b$ ja $c$: koneesta $a$ on yhteys koneeseen $b$ hintaan $c$. Jokainen yhteys on yksisuuntainen.

Voit olettaa, että alkutilanteessa warepalvelimelta on yhteys kaikkiin koneisiin.

Tuloste

Tulosta yksi kokonaisluku: pienin kokonaiskustannus lopullisessa verkossa.

Rajat

• $1 \le n \le 1000$
• $1 \le m \le 2000$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$

Esimerkki

Syöte:

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

Tuloste:

9

Selitys: Paras ratkaisu on valita yhteydet $1 \rightarrow 3$, $2 \rightarrow 4$ ja $3 \rightarrow 2$.