#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> d;
vector< pair<int,int> > q;
vector< vector< pair<int,int> > > v;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,x,y,c;
    scanf("%d%d",&n,&m);
    v.assign(n,vector< pair<int,int> >());
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);x--;y--;
        v[x].push_back(make_pair(y,c));
    }
    q.push_back(make_pair(0,0));
    d.assign(n,1000000000);
    d[0]=0;
    while(!q.empty())
    {
        pair<int,int> c=q.front();
        pop_heap(q.begin(),q.end()); q.pop_back();
        for(auto &x : v[c.second])
            if(d[x.first]>d[c.second]+x.second)
            {
                d[x.first]=d[c.second]+x.second;
                q.push_back(make_pair(d[x.first],x.first));
                push_heap(q.begin(),q.end());
            }
    }
    for(int i=1;i<n;i++)
        printf("%d%c",d[i]==1000000000?0:d[i],i==n-1?'\n':' ');
    return 0;
}