#include <bits/stdc++.h>
#define MAX 50100
#define INF 1e9

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

vector <pair <long long,long long> > G[MAX];
long long d[MAX],s[MAX],ctr[MAX];
long long n,m;
queue <long long> q;

void dostuff()
{
    long long x,y,c;

    fi>>n>>m;
    for(long long i=1;i<=m;i++)
    {
        fi>>x>>y>>c;
        G[x].push_back({y,c});
    }
}

void bf()
{
    long long nod,nxt,cst;

    q.push(1);
    s[1]=1;

    for(long long i=2;i<=n;i++)
        d[i]=INF;

    while(!q.empty())
    {
        nod=q.front();
        s[nod]=0;
        q.pop();

        for(long long i=0;i<G[nod].size();i++)
        {
            nxt=G[nod][i].first;
            cst=G[nod][i].second;

            if(cst+d[nod]<d[nxt])
                {d[nxt]=cst+d[nod];

                if(s[nxt]==0)
                {
                    s[nxt]=1;
                    q.push(nxt);
                }

                if(++ctr[nxt]>n)
                    return;
        }
    }
}
}

int main()
{
    dostuff();

    bf();

    for(long long i=2;i<=n;i++)
        fo<<d[i]<<" ";

    return 0;
}