#include <fstream>
#include <vector>
#include <set>
#define MAXN 50005
#define INF 50000005
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct muchie{
    long nod,cost;};
struct dist{
    long nod,d;};
struct comp{
    bool operator()(dist x,dist y) const{
        if(x.d==y.d)
            return x.nod<y.nod;
        else
            return x.d<y.d;}};

long n,m,a,b,c,cnt,df[MAXN];
vector<muchie> G[MAXN];
muchie aux;
dist t,v[MAXN],aux2;

int main()
{
    long i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        aux.nod=b;
        aux.cost=c;
        G[a].push_back(aux);}
    for(i=2;i<=n;i++){
        v[i].d=df[i]=INF;
        v[i].nod=i;}
    v[1].nod=1;
    set<dist,comp> s(v+1,v+n+1);
    while(cnt<n){
        t=*(s.begin());
        s.erase(s.begin());
        cnt++;
        for(i=0;i<G[t.nod].size();i++){
            aux=G[t.nod][i];
            if(t.d+aux.cost<df[aux.nod]){
                aux2.d=df[aux.nod];
                aux2.nod=aux.nod;
                s.erase(aux2);
                df[aux.nod]=t.d+aux.cost;
                aux2.d=df[aux.nod];
                s.insert(aux2);}}}
    for(i=2;i<=n;i++){
        if(df[i]>=INF)
            g<<"0 ";
        else
            g<<df[i]<<' ';}
    f.close();
    g.close();
    return 0;
}