#include <iostream>
#include <fstream>
#include <queue>
#define INFINIT 99999999
using namespace std;

struct nod
{
    int to,cost;
    nod *next;
};
struct lista
{
    nod *f,*l;
    lista()
    {
        f=l=NULL;
    }
};
lista graf[50001];
void add_node(int to,int cost,nod *&f,nod *&l)
{
    nod *c=new nod;
    c->to=to;
    c->cost=cost;
    c->next=NULL;
    if(f==l && f==NULL)
    {
        f=l=c;
    }
    else
    {
        l->next=c;
        l=c;
    }
}
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
void citire()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        add_node(b,c,graf[a].f,graf[a].l);
    }
}
void dijkstra()
{
    int *a=new int[n+1];
    for(int i=1;i<=n;i++)
        a[i]=INFINIT;
    a[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        for(nod *n=graf[k].f;n!=NULL;n=n->next)
        {
            int v=n->to;
            if(a[k]+n->cost<a[v])
            {
                a[v]=a[k]+n->cost;
                q.push(v);
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(a[i]==INFINIT)
            fout<<0<<" ";
        else fout<<a[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    return 0;
}