#include <fstream>
#include <set>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 50005;
const int INF = 0x3f3f3f3f;
int dist[NMAX];

vector <pair<int, int> > G[NMAX];

int main(){

    int n,m,i;
    f>>n>>m;
    for(i=0;i<m;++i){
        int from,to,cost;
        f>>from>>to>>cost;
        G[from].push_back(make_pair(to,cost));
    }

    memset(dist, INF, sizeof dist);

    dist[1]=0;

    set<pair<int, int> >h;

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

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

        for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); ++it){
            int to = it ->first;
            int cost = it ->second;

            if(dist[to]>dist[node]+cost){
                if(dist[to]!=INF)
                    h.erase(h.find(make_pair(dist[to],to)));

                dist[to]=dist[node]+cost;
                h.insert(make_pair(dist[to],to));
            }
        }
    }

    for(i=2;i<=n;++i)
        dist[i]!=INF? g<<dist[i]<<" " : g<<0<<" ";

        g<<'\n';

return 0;
}