#include <fstream>
#include <vector>
#include <set>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define mp make_pair
#define pb push_back
#define DMAX 50008
#define INF 1000000000
using namespace std;
ifstream fin(IN);
ofstream fout(OUT);

int n, m;
int dist[DMAX];
vector <int> graph[DMAX], cost[DMAX];
set< pair<int, int> > T;

void read();
void solve();

int main(){
    read();
    solve();

    int i;
    for (i = 2; i <= n; ++i)
        if (dist[i] == INF)
            fout <<0<<' ';
        else
            fout <<dist[i]<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}

void solve(){
    int i;
    for (i = 2; i <= n; ++i)
        dist[i] = INF;
    T.insert( mp(0, 1) );

    int val, x, dim;

    while (T.size()){
        val = T.begin()->first;
        x = T.begin()->second;
        T.erase(T.begin());

        dim = graph[x].size();
        for (i = 0; i < dim; ++i)
            if (val + cost[x][i] < dist[ graph[x][i] ]){
                dist[ graph[x][i] ] = val + cost[x][i];
                T.insert(mp( dist[ graph[x][i] ], graph[x][i] ));
            }
    }
}

void read(){
    fin >>n>>m;

    int i;
    int a, b, c;
    for (i = 0; i < m; ++i){
        fin >>a>>b>>c;
        graph[a].pb(b);
        cost[a].pb(c);
    }
}