#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>

#define pii pair<int,int>

using namespace std;
const int nmax = 50005;
const int inf = (1LL<<31)-1;

int i,n,m,x,y,z,d[nmax];

vector<pii> v[nmax];

bitset<nmax> viz;

priority_queue<pii,vector<pii>,greater<pii> > 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",&x,&y,&z);
        v[x].push_back(make_pair(y,z));
    }

    for(i=2;i<=n;i++) d[i]=inf;
    q.push(make_pair(0,1));

    while(!q.empty())
    {
        x=q.top().second;
        q.pop();

        if(viz[x]) continue;
        viz[x]=1;

        for(vector<pii>::iterator it=v[x].begin();it!=v[x].end();it++)
            if(d[x]+it->second<d[it->first])
            {
                d[it->first]=d[x]+it->second;
                q.push(make_pair(d[it->first],it->first));
            }
    }

    for(i=2;i<=n;i++)
    {
        if(d[i]==inf) printf("0 ");
        else printf("%d ",d[i]);
    }

    return 0;
}