#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("dbz.in");
ofstream fout("dbz.out");

const int inf = 2e9;

struct NodeCost {
    int node, cost;
    bool operator<(const NodeCost other) const {
        return this->cost > other.cost;
    }
};

struct Edges {
    int xx, yy, cc;
};

int N, M;
int d[1505], t[1505];
Edges e[30005];
priority_queue<NodeCost> pq;
vector<NodeCost> g[1505];
bool v[1505];

int Dijkstra(int s) {
    for (int i = 1; i <= N; i++) {
        d[i] = inf;
        t[i] = 0;
        v[i] = false;
    }

    d[s] = 0;
    pq.push({s, 0});

    while (!pq.empty()) {
        int currentNode = pq.top().node;
        pq.pop();

        if (v[currentNode]) { continue; }

        v[currentNode] = true;
        for (auto muchie: g[currentNode]) {
            int vecin = muchie.node, dist = muchie.cost;

            if (d[currentNode] + dist < d[vecin]) {
                d[vecin] = d[currentNode] + dist;
                pq.push({vecin, d[vecin]});

                if (currentNode == s) {
                    t[vecin] = vecin;
                } else {
                    t[vecin] = t[currentNode];
                }
            }
        }
    }

    t[s] = s;
    int res = inf;

    for (int i = 1; i <= M; i++) {
        int x = e[i].xx;
        int y = e[i].yy;
        int c = e[i].cc;

        if (t[x] != t[y] && ((x != s && y != s) || t[x] != x || t[y] != y)) {
            res = min(res, d[x] + d[y] + c);
        }
    }

    if (res != inf) { return res; }
    return -1;
}

int main() {
    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({y, c});
        g[y].push_back({y, c});
        e[i] = {x, y, c};
    }

    for (int i = 1; i <= N; i++) {
        fout << Dijkstra(i) << ' ';
    }
    return 0;
}