#include <bits/stdc++.h>
using P = std::pair<int, int>;
const int INF = 1e9;
int n, m;
std::vector<std::vector<P>> edges;
std::set<P> used;
int D[110];
std::vector<std::set<P>> us;
inline P mp(int x, int y) {
  if (x > y) {
    std::swap(x, y);
  }
  return {x, y};
}
void dijkstra(int s) {
  for (int i = 0; i < n; ++i) {
    D[i] = INF;
  }
  us.clear();
  us.resize(n);
  D[s] = 0;
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;
  que.push({0, s});
  while (!que.empty()) {
    auto p = que.top();
    que.pop();
    if (p.first > D[p.second]) {
      continue;
    }
    for (auto& q : edges[p.second]) {
      if (D[q.first] > D[p.second] + q.second) {
        us[q.first].clear();
        us[q.first].insert(mp(p.second, q.first));
        D[q.first] = D[p.second] + q.second;
        que.push({D[q.first], q.first});
      } else if (D[q.first] == D[p.second] + q.second) {
        us[q.first].insert(mp(p.second, q.first));
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (auto& p : us[i]) used.insert(p);
  }
}
int main() {
  std::cin >> n >> m;
  edges.resize(n);
  for (int i = 0; i < m; ++i) {
    int x, y, z;
    std::cin >> x >> y >> z;
    edges[--x].push_back({--y, z});
    edges[y].push_back({x, z});
  }
  for (int i = 0; i < n; ++i) {
    dijkstra(i);
  }
}
