#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 2147483647
int n,m,v[50001],i,x,y,z,j,k,e,w,l[50001],qq,xx;
bool t[50001];
struct nod
{
    int x,c;
}q;
vector < nod > a[50001];
queue <int> coada;
int main()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>x>>q.x>>q.c;
        /*if(x<q.x)*/a[x].push_back(q);++l[x];
    }
    f.close();
    ++n;
    for(i=2;i<n;++i){v[i]=MAX;t[i]=0;}
    //--n;
    //FA PARCURGERE,NU LUA NODURILE DUPA NUMAR!!!!
    coada.push(1);//t[1]=1;
    while(!coada.empty())
    {
        i=coada.front();t[i]=1;coada.pop();
        //cout<<i<<":";
        k=l[i];//cout<<k<<" ";
        for(j=0;j<k;++j)
        {
            e=a[i][j].c+v[i];
            w=a[i][j].x;
            xx=a[i][j].x;qq=a[i][j].c;
            if(e<v[w])
            {
                v[w]=a[i][j].c+v[i];
            }
            //cout<<w<<" "<<t[w]<<'\n';
            if(t[w]<1)coada.push(w);
        }
    }
    ofstream g("dijkstra.out");
    //++n;
    for(i=2;i<n;++i)g<<v[i]<<" ";
    return 0;
}