#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int INF=999999999;
const int N=250001;

int n,m,d[N],h[N],poz[N],nh;
vector <int> a[N];
vector <int> c[N];


void swapp( int p, int q)
{
    swap( h[p], h[q] );
    poz[ h[p] ]=p;
    poz[ h[q] ]=q;
}

void coboara (int p)
{
    int fs=2*p,fd=2*p+1,bun=p;

    if (fs<=nh && d[ h[fs] ] < d[ h[bun] ])
        bun=fs;

    if (fd<=nh && d[ h[fd] ] < d[ h[bun] ])
        bun = fd;
    if (bun != p)
    {
        swapp ( p, bun );
        coboara (bun);
    }
}

void urca (int p)
{
    while ( p>1 && d[ h[p] ] < d[ h[p/2] ] )
    {
        swapp( p, p/2 );
        p/=2;
    }
}

void sterge (int p)
{
    swapp ( p, nh-- );
    urca(p);
    coboara (p);
}

void dijkstra (int x0)
{
    int x,y,cost;
    for (int i=1; i<=n; i++)
    {
        d[i]=INF;
        h[i]=i;
        poz[i]=i;
    }
    d[x0]=0;
    urca (poz[x0]);
    nh=n;
    while (nh>0 && d[ h[1] ] != INF)
    {
        x=h[1];
        sterge(1);
        for (int i=0; i<a[x].size(); i++)
        {
            y=a[x][i];
            cost=c[x][i];
            if (d[x]+cost<d[y])
            {
                d[y]=d[x]+cost;
                urca(poz[y]);
            }
        }
    }
}
int main()
{
    int i,x,y,cost;
    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        a[x].push_back(y);
        c[x].push_back(cost);
    }
    dijkstra(1);
    for (i=2; i<=n; i++)
    {
        if (d[i]==INF)
            g<<0<<" ";
        else g<<d[i]<<" ";
    }
    return 0;
}