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

using namespace std;

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

set <pair <int,int>> g[50010];

int d[50010], f[50010];

int main() {
    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int u, v, cost;
        fin >> u >> v >> cost;
        g[u].insert({v, cost});
    }

    for(int i = 1; i <= n; ++i) d[i] = 1e9;

    for(auto v : g[1])
        d[v.first] = v.second;

    f[1] = 1, d[1] = 0;
    d[0] = 1e9;
    int pmax = 1;
    while(pmax != 0) {
        pmax = 0;

        for(int i = 1; i <= n; ++i)
            if(f[i] == 0 && d[i] < d[pmax] && d[i] != 0)
                pmax = i;

        if(pmax != 0) {
            f[pmax] = 1;
            for(auto v : g[pmax])
                if(f[v.first] == 0 && d[v.first] > d[pmax] + v.second)
                    d[v.first] = d[pmax] + v.second;
        }
    }

    for(int i = 2; i <= n; ++i)
        if(d[i] < 1e9) fout << d[i] << " ";
        else fout << "0 ";

    return 0;
}