#include <algorithm>
#include <iostream>
#include <vector>

struct dato {
   int vertice;
   int costo;
};

int main( ) {
   int n, m;
   std::cin >> n >> m;
   n += 1;                                   // por el vértice ficticio (que será el n - 1 para evitar reenumerar los índices de los demás vértices)

   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));
   }
   for (int i = 0; i < n - 1; ++i) {
      listas[n - 1].push_back(dato(i, 0));   // arcos del vértice ficticio a todos los demás
   }

   std::vector<int> potenciales(n, 1e9);     // los potenciales son las distancias de la ejecución inicial de Bellman-Ford
   potenciales[n - 1] = 0;                   // comenzando desde el vértice ficticio
   for (int k = 0; k < n - 1; ++k) {
      for (int i = 0; i < n; ++i) {
         if (potenciales[i] != 1e9) {
            for (dato d : listas[i]) {
               potenciales[d.vertice] = std::min(potenciales[d.vertice], potenciales[i] + d.costo);
            }
         }
      }
   }

   n -= 1;                                   // volvemos a concentrarnos en los vértices originales de la gráfica
   std::vector<std::vector<int>> distancias(n, std::vector<int>(n, 1e9));
   for (int i = 0; i < n; ++i) {
      for (dato d : listas[i]) {
         distancias[i][d.vertice] = d.costo + potenciales[i] - potenciales[d.vertice];    // costos de los arcos de la nueva gráfica (ya no son negativos)
      }
   }
   for (int i = 0; i < n; ++i) {
      distancias[i][i] = 0;
   }

   for (int k = 0; k < n; ++k) {             // usaremos floyd sobre la nueva gráfica
      for (int i = 0; i < n; ++i) {
         for (int j = 0; j < n; ++j) {
            distancias[i][j] = std::min(distancias[i][j], distancias[i][k] + distancias[k][j]);
         }
      }
   }

   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
         if (distancias[i][j] != 1e9) {
            std::cout << i << " " << j << ": " << distancias[i][j] - potenciales[i] + potenciales[j] << "\n";     // recuperación del costo real del camino más corto
         } else {
            std::cout << i << " " << j << ": " << distancias[i][j] << "\n";
         }
      }
   }
}

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