#include <cstdio>
#include <queue>
#include <limits.h>
#include <vector>
#define MAX 50000000
using namespace std;

int n,m,D[50010],viz[50010],nr[50010],nrr;
vector< pair<int,int> >v[50010];
priority_queue  < pair<int,int> > q;
int main()
{
    pair<int,int> aux;
    int i,x,y,c,nod,cost;
    FILE *f=fopen("dijsktra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=2;i<=n;i++)D[i]=MAX;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[x].push_back(make_pair(c,y));
        if(x==1)
        {
            q.push(make_pair(-c,y));
            D[y]=c;
        }
        nr[x]++;
    }
    viz[1]=1;
    while(!q.empty())
    {
        aux=q.top();
        nod=aux.second;
        cost=-aux.first;
        if(!viz[nod])
        {
            viz[nod]=1;
            D[nod]=cost;
            nrr=nr[nod];
            for(i=0;i<nrr;i++)
                {
                    aux=v[nod][i];
                    if(aux.first+cost<D[aux.second])
                    {
                        D[aux.second]=aux.first+cost;
                        q.push(make_pair(-D[aux.second],aux.second));
                    }
                }
        }
        q.pop();
    }
    for(i=2;i<=n;i++)fprintf(g,"%d ",D[i]==MAX?0:D[i]);
    fclose(f);
    fclose(g);
    return 0;
}