#include <cstdio>
#include <vector>
#include <utility>
#define pb push_back
#define mp make_pair
#define nmax 50005
#define inf 1000000
using namespace std;
FILE *f1=fopen("dijkstra.in","r"),*f2=fopen("dijkstra.out","w");
vector <pair<int,int> >g[nmax];
int n,m,nr;
int dMin[nmax],pozHeap[nmax],heap[nmax];

// == update heap ==
void updateHeap(int poz)
{
    while(poz>=1&&dMin[heap[poz]]<dMin[heap[(poz-1)/2]])
    {
        swap(pozHeap[heap[poz]],pozHeap[heap[(poz-1)/2]]);
        swap(heap[poz],heap[(poz-1)/2]);
        poz=(poz-1)/2;
    }
}
// == extrage minim din heap ==
int extract()
{
    int minim,fiu,i=0;
    minim=heap[0];
    nr--;
    pozHeap[heap[0]]=pozHeap[heap[nr]];
    heap[0]=heap[nr];
    do
    {
        fiu=0;
        if(2*i+1<nr)
        {
            fiu=2*i+1;
            if(2*i+2<nr&&dMin[heap[2*i+2]]<dMin[heap[2*i+1]])
            fiu++;
            if(dMin[heap[i]]<=dMin[heap[fiu]])fiu=0;
        }
        if(fiu)
        {
            swap(pozHeap[heap[i]],pozHeap[heap[fiu]]);
            swap(heap[i],heap[fiu]);
            i=fiu;
        }
    }while(fiu);
    return minim;
}
// == Citire ==
void citire()
{
    int i,x,y,c;
    fscanf(f1,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
        {
            dMin[i]=inf;
            heap[i-1]=i;
            pozHeap[i]=i-1;
        }
    nr=n;
    for(i=1;i<=m;i++)
    {
        fscanf(f1,"%d %d %d",&x,&y,&c);
        g[x].pb(mp(y,c));
        if(x==1)
        {
            dMin[y]=c;
            updateHeap(pozHeap[y]);
        }
    }
}
// == Dijkstra ==
void dijkstraHeap()
{
    int i,j,vfMin;
    for(j=1;j<n;j++)
    {
        vfMin=extract();
        for(i=0;i<g[vfMin].size();i++)
        if(dMin[g[vfMin][i].first]>dMin[vfMin]+g[vfMin][i].second)
        {
            dMin[g[vfMin][i].first]=dMin[vfMin]+g[vfMin][i].second;
            updateHeap(pozHeap[g[vfMin][i].first]);
        }
    }
}
void afis()
{
    int i;
    for(i=2;i<=n;i++)
        fprintf(f2,"%d ",
        dMin[i]==inf?0:
                dMin[i]);
}
int main()
{
    citire();
    dijkstraHeap();
    afis();
    return 0;
}