#include<fstream>
#include<vector>
#include<queue>
#define MAX 50002
#define inf (1<<30)
#define pb push_back
#define mp make_pair
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int x,y,c,N,M,d[MAX],nc;
bool viz[MAX];
vector<pair<int,int> >a[MAX];
struct compara
{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }
};
priority_queue<int,vector<int>,compara>q;
void citire()
{
    in>>N>>M;
    for(int i=0;i<M;i++)
    {
        in>>x>>y>>c;
        a[x].pb(mp(y,c));
    }
}
void dijkstra()
{
    for(int i=2;i<=N;i++)
        d[i]=inf;
    d[1]=0;
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        nc=q.top();
        q.pop();
        viz[nc]=0;
        for(unsigned i=0;i<a[nc].size();i++)
        {
            if((a[nc][i].second+d[nc]<d[a[nc][i].first])&(!viz[a[nc][i].first]))
            {
                d[a[nc][i].first]=a[nc][i].second+d[nc];
                q.push(a[nc][i].first);
                viz[a[nc][i].first]=1;
            }
        }
    }
}
void afisare()
{
    for(int i=2;i<=N;i++)
        out<<d[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    afisare();
}