#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].second<val[v[nod][i].first])
        {
            val[v[nod][i].first]=val[nod]+v[nod][i].second;
            if(exp[v[nod][i].first]==0)q.push(make_pair(v[nod][i].first,val[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(y,c));
    }
    for(int i=1;i<=n;i++)val[i]=INF;
    val[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty())
    {
        pair<int,int> nod=q.top();
        q.pop();
        if(exp[nod.first]==0)parc(nod.first);
    }
    for(int i=2;i<=n;i++)
        if(val[i]!=INF)fout<<val[i]<<" ";
    else fout<<"0 ";
    return 0;
}