Problem
Le président de Berland s'est tourné vers vous pour obtenir de l'aide ! Il y a n villes dans son pays. Il existe des routes à double sens entre certaines paires de villes. La saison touristique va s'ouvrir très prochainement, mais les routes de Berland ne sont pas du tout prêtes pour une telle épreuve.
Le président veut réparer un ensemble de routes afin que le coût total des réparations soit minime et que l'on puisse se rendre de n'importe quelle ville de Berland à n'importe quelle autre en utilisant uniquement les routes réparées.
Trouvez beaucoup de routes qui doivent être réparées, votre ami vous aidera. Il vous suffit de calculer le coût de réparation minimum.
Il est garanti qu'il y a toujours un ensemble de routes requis.
Saisie :
La première ligne contient deux entiers - n et m (2 <= n <= 300000, n - 1 <= m <= 300000).
Les m lignes suivantes contiennent trois nombres - u, v et w (1 <= u, v <= n, 0 <= w <= 109) - la route entre les villes u et v dont le coût de réparation est w.