В первой строке входных данных находятся числа N и M (1 <= N <= 100; 1 <= M <= 6000), где N – количество вершин в графе, а M – количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B – номера вершин, соединённых ребром, а C – вес ребра (натуральное число, не превышающее 30000)