#include<iostream>
#include<queue>
#include<fstream>
#include<vector>
#include<cstring>
#define inf 0x3f3f3f3f

using namespace std;
int n,m,d[50005];
queue <int> q;
bool viz[50005];
//long long c[5000][5000];
vector <pair<int,int> >g[50005];


void dijkstra(int x)
{
   /* int i,j,min,k,ok;
    int viz[50000],tata[50000];
    for(i=1;i<=n;++i)
    {
        d[i]=c[x][i];
        tata[i]=x;
        viz[i]=0;
    }
    tata[x]=0;
    viz[x]=1;
    ok=1;
    while(ok)
    {
        min=99999;
        for(i=1;i<=n;++i)
            if(!viz[i] && min>d[i])
            {
                min=d[i];
                k=i;
            }
        if(min!=99999)
        {
            viz[k]=1;
            for(i=1;i<=n;++i)
                if(!viz[i] && d[i]>d[k]+c[k][i])
                {
                    d[i]=d[k]+c[k][i];
                    tata[i]=k;
                }
        }
        else
         ok=0;
    }*/
    int k;
    q.push(1);
    d[1]=0;
    viz[1]=1;
    while(!q.empty())
    {
        k=q.front();
        vector <pair<int,int> >::iterator i;
        viz[k]=0;
        q.pop();
        for(i=g[k].begin();i!=g[k].end();++i)
        {
            if(d[i->first]>d[k]+i->second)
            {
                d[i->first]=d[k]+i->second;
                if(viz[i->first]==0)
                {
                    viz[i->first]=1;
                    q.push(i->first);
                }
            }
        }
    }

}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int i,a,b,j,c;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    memset(d,inf,sizeof(d));
   /* for(i=1;i<=n;++i)
        dijkstra(i);*/
    dijkstra(1);
    for(i=2;i<=n;++i)
    {
        /*for(j=1;j<=n;++j)
            fout<<c[i][j]<<" ";
        fout<<"\n";*/
        if(d[i]!=inf)
            fout<<d[i]<<" ";
        else fout<<0<<" ";
    }
    return 0;
}