#include using namespace std; template using vec = vector; template using vvec = vec>; template using lqueue = priority_queue, greater>; template using gqueue = priority_queue, less>; int main() { constexpr int64_t inf = INT64_MAX / 2; int n, m; cin >> n >> m; vvec dist(n, vec(n, inf)); for (int i = 0; i < n; ++i) dist[i][i] = 0; for (int i = 0; i < m; ++i) { int64_t s, t, d; cin >> s >> t >> d; --s; --t; dist[s][t] = min(dist[s][t], d); } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } for (auto &e1 : dist) for (auto &e2 : e1) { if (e2 == inf) e2 = 0; } for (int i = 0; i < n; ++i) { cout << accumulate(begin(dist[i]), end(dist[i]), int64_t(0)) << endl; } }