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

#define oo 250000000

using namespace std;

int n;
vector< pair<int, int> > L[50005];
queue<int> q;
int d[50005];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int m, x, y, c;
    f >> n >> m;
    for(int i = 2; i <= n; i ++) d[i] = oo;
    for(; m; m --) {
        f >> x >> y >> c;
        L[x].push_back({y, c});
    }

    q.push(1);
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(int i = 0; i < L[v].size(); i ++) {
            if(d[L[v][i].first] > d[v] + L[v][i].second) {
                q.push(L[v][i].first);
                d[L[v][i].first] = d[v] + L[v][i].second;
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        if(d[i] == oo) g << "0 ";
        else g << d[i] << " ";
    g << "\n";
    return 0;
}