#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
struct bla
{
    int nod,urm,cost;
} t[510010];
int start[51010];
int n,m,d[51010];
int nr;
struct two
{
    int varf,value;
} heap[51010];
void read ()
{ int a,b,c,k=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        t[++k].nod=b; t[k].urm=start[a]; start[a]=k; t[k].cost=c;
    }
}
void climb (int poz)
{
    while(3>2)
    {
        if(poz>1 && heap[poz].value<heap[poz/2].value)
            swap(heap[poz],heap[poz/2]),poz/=2;
        else break;
    }
}
void down (int poz)
{
    int fiu=0;
    while(3>2)
    {
        if(poz*2<=nr) fiu=poz*2;
        if(poz*2+1<=nr && heap[poz*2+1].value<heap[fiu].value) fiu++;
        if(fiu && heap[poz].value>heap[fiu].value)
            swap(heap[poz],heap[fiu]),poz=fiu;
        else break;
    }
}
void dijkstra ()
{
    heap[++nr].varf=1;
    heap[nr].value=0;
    while(nr)
    {
        for(int x=start[heap[1].varf];x;x=t[x].urm)
        {
            if(heap[1].value+t[x].cost<d[t[x].nod]) d[t[x].nod]=heap[1].value+t[x].cost,heap[++nr].varf=t[x].nod,heap[nr].value=d[t[x].nod],climb(nr);
        }
        heap[1]=heap[nr--];
        down(1);
    }
}
void write ()
{
    for(int i=2;i<=n;i++) {if(d[i]==INT_MAX) d[i]=0; cout<<d[i]<<" ";}
}
void init ()
{
    for(int i=2;i<=n;i++) d[i]=INT_MAX;
}
int main()
{
    read();
    init();
    dijkstra();
    write();
    cin.close();
    cout.close();
    return 0;
}