#include <cstdio>
#include <vector>
#include <limits.h>

#define inf INT_MAX/2
#define res1 50000
#define res2 250000

using namespace std;

vector<pair<int,int> > graf[res1];
int n,m,viz[res1],dist[res1],tata[res1];

FILE *f1,*f2;
int main()
{
    f1= fopen("dijkstra.in","r");
    f2=fopen("dijkstra.out","w");
    fscanf(f1,"%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        tata[i]=-1;
        dist[i]=inf;
    }
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        fscanf(f1,"%d%d%d",&a,&b,&c);
        graf[a].push_back(make_pair(b,c));
    }
    viz[1]=1;
    tata[1]=0;
    vector<pair<int,int> > ::iterator it;
    for(it=graf[1].begin(); it!=graf[1].end(); it++)
    {
        dist[it->first]=it->second;
        tata[it->first]=1;
    }
    dist[1]=0;
    for(int i=1; i<=n-2; i++)
    {
        int dmin=inf;
        int k=-1;
        for(int j=1; j<=n; j++)
            if(!viz[j]&&dist[j]<dmin)
                dmin=dist[k=j];
        if(k==1)
            break;
        viz[k]=1;
        for(it=graf[k].begin();it!=graf[k].end();it++)
        {
            if(dist[k]+it->second<dist[it->first])
            {
                dist[it->first]=dist[k]+it->second;
                tata[it->first]=k;
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        fprintf(f2,"%d ",dist[i]==inf?0:dist[i]);
    }

    return 0;
}