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

int n,m,D[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));
    }
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        aux=q.top();
        q.pop();
        nod=aux.second;
        cost=-aux.first;
        for(i=0;i<v[nod].size();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));
                }
            }
    }
    for(i=2;i<=n;i++)fprintf(g,"%d ",D[i]==MAX?0:D[i]);
    fclose(f);
    fclose(g);
    return 0;
}