#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n,i,j,cate[50005],dist[50005],nou,m,p,x,y,cost,el,viz[50005];
typedef pair <long long, int > per;
vector <int> liste[50005]; vector <int> listeval[50005];
priority_queue <per, vector <per> , greater <per> > q;
void actual(int nod)
{
    for(int i=0;i<=cate[nod]-1;i++)
    {
        nou=liste[nod][i];
        if(dist[nod]+listeval[nod][i]<dist[nou])
        {
            dist[nou]=dist[nod]+listeval[nod][i];
            q.push(make_pair(dist[nou],nou));
        }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        liste[x].push_back(y);
        listeval[x].push_back(cost);
        cate[x]++;
    }
    for(int i=0;i<=n;i++) dist[i]=1999999999;
    q.push(make_pair(0,1));
    dist[1]=0;
    while(q.size()>=1)
    {
        el=q.top().second;
        if(viz[el]==0)
        {
            viz[el]=1;
            q.pop();
            actual(el);
        }
        else q.pop();
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]==1999999999) fout<<0<<' ';
        else fout<<dist[i]<<' ';
    }
    return 0;
}