#include <cstdio>
#include <vector>
#include <queue>
#define N 50010
#define oo 50000010
using namespace std;
int n,m,i,d[N],a,b,c,x;
vector<pair<int,int> >v[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;i++)
        d[i]=oo;
    Q.push(make_pair(0,1));
    for(;Q.size();)
    {
        x=Q.top().second;
        Q.pop();
        for(vector<pair<int,int> >::iterator it=v[x].begin();it!=v[x].end();it++)
            if(d[it->first]>d[x]+it->second)
            {
                d[it->first]=d[x]+it->second;
                Q.push(make_pair(d[it->first],it->first));
            }

    }
    for(i=2;i<=n;i++)
        d[i]==oo?printf("0 "):printf("%d ",d[i]);
    return 0;
}