#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF (1<<30)
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int val[50005],exp[50005],mn,ind,n,m,x,y,c;
pair <int,int> nr;
vector <pair<int,int> > v[50005],act;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void parc(int nod)
{
    exp[nod]=1;
    for(int i=0;i<v[nod].size();i++)
    {
        if(val[nod]+v[nod][i].first<val[v[nod][i].second])
        {
            val[v[nod][i].second]=val[nod]+v[nod][i].first;
            if(exp[v[nod][i].second]==0)q.push(make_pair(val[v[nod][i].second],v[nod][i].second));
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(c,y));
    }
    for(int i=1;i<=n;i++)val[i]=INF;
    val[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int nod=q.top().second;
        q.pop();
        if(exp[nod]!=1)parc(nod);
    }
    for(int i=2;i<=n;i++)
        if(val[i]!=INF)fout<<val[i]<<" ";
    else fout<<"0 ";
    return 0;
}