#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50002
#define inf 0x3f3f3f3f
#define pii pair<int,int>

using namespace std;

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

int i,n,m,d[Nmax];
bool used[Nmax];
vector<pii> g[Nmax]; // pii e definit mai sus ca pair<int,int>
                     // primul int din pereche e nodul vecin
                     // al doilea int e lungimea muchiei

struct cmp{
    inline bool operator() (const int &a,const int &b){
        return d[a]>d[b];
    }
};

priority_queue<int,vector<int>,cmp> q;

void dijkstra(int start){
    int nod,v,c,l;
    for(i=1;i<=n;++i)
        d[i]=inf;
    d[start]=0;

    q.push(1);
    while(!q.empty()){
        nod=q.top();
        q.pop();
        if(used[nod])
            continue;

        used[nod]=true;
        l=g[nod].size();
        for(int i=0;i<l;++i){
            v=g[nod][i].first; // nodul vecin
            c=g[nod][i].second+d[nod]; // lungimea muchiei + distanta parcursa pana la nodul "nod"
            if(c<d[v]){
                d[v]=c;
                q.push(v);
            }
        }
    }
}

int main()
{
    int x,y,c;
    f >> n >> m;
    for(i=1;i<=m;++i){
        f >> x >> y >> c;
        g[x].push_back(make_pair(y,c)); // functia make_pair creeaza o pereche intre nodul vecin(y) si lungimea muchiei(c)
    }

    dijkstra(1);


    for(i=1;i<=n;++i){
        if(i==1) // daca e nodul de start
            continue;

        if(d[i]==inf)
            o << 0 << " ";
        else
            o << d[i] << " ";
    }
    return 0;
}