#include <iostream>
#include <queue>
#include <vector>

struct dato {
   int vertice;
   int costo;
};

bool operator<(dato d1, dato d2) {
   return d1.costo > d2.costo;
}

int main( ) {
   int n, m;
   std::cin >> n >> m;

   std::vector<std::vector<dato>> listas(n);
   for (int i = 0; i < m; ++i) {
      int v1, v2, c;
      std::cin >> v1 >> v2 >> c;
      listas[v1].push_back(dato(v2, c));
      listas[v2].push_back(dato(v1, c));
   }

   std::vector<int> distancias(n, -1);
   std::priority_queue<dato> cp;
   cp.push(dato(0, 0));

   while (!cp.empty( )) {
      dato d = cp.top( );
      cp.pop( );
      if (distancias[d.vertice] == -1) {
         distancias[d.vertice] = d.costo;
         for (dato a : listas[d.vertice]) {
            cp.push(dato(a.vertice, d.costo + a.costo));
         }
      }
   }

   for (int i = 0; i < n; ++i) {
      std::cout << i << ": " << distancias[i] << "\n";
   }
}

/* ejemplo de entrada
4
6
0 1 1
0 2 5
0 3 2
1 2 2
1 3 4
2 3 1
*/