#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int nr2,aux,nr,x1,y1,c1,i,n,m,ul,ok,heap[50009],b[50009],poz[50009],c[50009];
vector < pair < int , int > > v[50009];
vector < pair < int , int > >::iterator it;
int cmp(int p1,int p2)
{
    ///////1 dac p1<=p2
    if(b[heap[p1]]<=b[heap[p2]]) return 1;
    return 0;
}
void swap(int p1,int p2)
{
    int aux=heap[p1];
    poz[aux]=p2;
    poz[heap[p2]]=p1;
    heap[p1]=heap[p2];
    heap[p2]=aux;
}
void heapup(int p)
{
    if(p==1) return ;
    if(!cmp(p>>1,p))
    {
        swap(p>>1,p);
        heapup(p>>1);
    }
}
void heapdown(int p)
{
    int f;
    if((p<<1)>nr) return ;
    f=(p<<1);
    if(f+1<=nr&&cmp(f+1,f))
        f++;
    if(cmp(f,p))
    {
        swap(f,p);
        heapdown(f);
    }
}
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
    scanf("%d",&x1);
    scanf("%d",&y1);
    scanf("%d",&c1);
    v[x1].push_back(make_pair(y1,c1));
}
ul=1;
b[1]=0;
for(i=2;i<=n;i++)
{
    b[i]=c[i]=10000000;
    nr++;
    heap[nr]=i;
    poz[i]=nr;
}
ok=1;
nr2=nr;
while(nr2>=0)
{
    ok=0;
    for(it=v[ul].begin();it!=v[ul].end();it++)
        if(c[ul]+it->second<c[it->first])
        {
            if(b[it->first]==100000000)
            {
                c[it->first]=c[ul]+it->second;
                continue;
            }
            c[it->first]=b[it->first]=c[ul]+it->second;
            heapup(poz[it->first]);
            ok=1;
        }
    if(nr2==0) break;
    ul=heap[1];
    aux=b[ul];
    b[ul]=100000000;
    c[ul]=aux;
    nr2--;
    heapdown(1);
    //b[ul]=aux;
}
for(i=2;i<=n;i++)
{
    if(c[i]>=10000000) printf("0 ");
    else printf("%d ",c[i]);
}
return 0;
}