#include <bits/stdc++.h>
using namespace std;

int n,m1;
vector<pair<int,int> > m[50010];
int d[50010];

void dij(int nod)
{
    for(vector<pair<int,int> >::iterator it=m[nod].begin();it!=m[nod].end();it++)
        if( d[it->first ]> d[nod] + it->second )
        {
            d[it-> first]=d[nod]+it->second;
            dij(it->first);
        }
}

int main()
{
    int i,n1,n2,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(;m1;m1--)
    {
        scanf("%d%d%d",&n1,&n2,&c);
        m[n1].push_back( make_pair(n2,c) );
    }
    for(i=1;i<=n;i++) d[i]=0x7ffffff;
    d[1]=0;
    dij(1);
    for(i=2;i<=n;i++) cout<<d[i]<<' ';
    fclose(stdin);
    fclose(stdout);
    return 0;
}