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

struct dato {
   int vertice;
   int costo;
};

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

   std::vector<std::vector<int>> distancias(n, std::vector<int>(n, 1e9));
   for (int i = 0; i < m; ++i) {
      int v1, v2, c;
      std::cin >> v1 >> v2 >> c;
      distancias[v1][v2] = c;
      distancias[v2][v1] = c;
   }
   for (int i = 0; i < n; ++i) {
      distancias[i][i] = 0;
   }

   for (int k = 0; k < n; ++k) {
      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) {
         std::cout << i << " " << j << ": " << distancias[i][j] << "\n";
      }
   }
}

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