#include <cstdio>
#include <vector>
using namespace std;
vector <int> v[50004],v1[50004];
int nr,aux,x,y,l,h[50004],poz[50004],poz1[50004],i,j,pos,n,m,k,b[50004];
void HeapUp (int x)
{
    if (x>1)
    {
        if (h[x]<h[x/2])
        {
            aux=h[x];
            h[x]=h[x/2];
            h[x/2]=aux;
            aux=poz[x];
            poz[x]=poz[x/2];
            poz[x/2]=aux;
            aux=poz1[poz[x]];
            poz1[poz[x]]=poz1[poz[x/2]];
            poz1[poz[x/2]]=aux;
            HeapUp(x/2);
        }
    }
}
void HeapDown (int x)
{
    if (2*x<=nr)
    {
        int i;
        if ((2*x+1)>nr || h[2*x]<h[2*x+1])
            i=2*x;
        else
            i=2*x+1;
        if (h[i]<h[x])
        {
            aux=h[x];
            h[x]=h[i];
            h[i]=aux;
            aux=poz[x];
            poz[x]=poz[i];
            poz[i]=aux;
            aux=poz1[poz[x]];
            poz1[poz[x]]=poz1[poz[i]];
            poz1[poz[i]]=aux;
            HeapDown(i);
        }
    }
}
int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    scanf ("%d %d", &n, &m);
    for (i=1;i<=m;i++)
    {
        scanf ("%d %d %d", &x, &y, &l);
        v[x].push_back(y);
        v1[x].push_back(l);
    }
    k=v[1].size();
    for (i=0;i<=(k-1);i++)
    {
        h[++nr]=v1[1][i];
        poz[nr]=v[1][i];
        poz1[v[1][i]]=nr;
        HeapUp(nr);
    }
    for (i=1;i<=n;i++)
        b[i]=-1;
    for (j=1;j<=(n-1);j++)
    {
        pos=poz[1];
        b[pos]=h[1];
        h[1]=h[nr];
        poz[1]=poz[nr];
        poz1[poz1[1]]=1;
        nr--;
        HeapDown(1);
        k=v[pos].size();
        for (i=0;i<=(k-1);i++)
        {
            if (b[v[pos][i]]==-1)
            {
            if (h[poz1[v[pos][i]]]>(b[pos]+v1[pos][i]))
            {
                h[poz1[v[pos][i]]]=b[pos]+v1[pos][i];
                HeapUp(poz1[v[pos][i]]);
            }
            else if (poz1[v[pos][i]]==0)
            {
                nr++;
                h[nr]=b[pos]+v1[pos][i];
                poz[nr]=v[pos][i];
                poz1[v[pos][i]]=nr;
                HeapUp(nr);
            }
            }
        }
    }
    for (i=2;i<=n;i++)
    {
        if (b[i]!=-1)
            printf ("%d ", b[i]);
        else
            printf ("%d", 0);
    }
    return 0;
}