#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMAX = 1005;
const int INF = 1000005;

vector<pair<int, int>> G[NMAX];
int dist[NMAX];
set<pair<int, int>> h;

int n;

int main() {

    int m;
    in>>n>>m;

    int start = 1;

    for(int i=1; i<=m; i++) {
        int x, y, d;
        in>>x>>y>>d;
        G[x].push_back(make_pair(y, d));
    }

    for(int i=1; i<=n; i++)
        dist[i]=INF;
    dist[start] = 0;

    h.insert(make_pair(0, start));

    while (!h.empty()) {
        int nod = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        for (vector<pair<int, int>>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
            int y = it->first;
            int cost = it->second;
            if (dist[y] > dist[nod] + cost) {
                if (dist[y] != INF) {
                    h.erase(h.find(make_pair(dist[y], y)));
                }
                dist[y] = dist[nod] + cost;
                h.insert(make_pair(dist[y], y));
            }
        }
    }

    for (int i=1; i<=n; i++) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }
    }

    for (int i=2; i<=n; i++) {
        out<<dist[i]<<' ';
    }

    return 0;
}