#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX 2147483647
int n,m,v[50001],i,x,y,z,j,k,e,w,l[50001],qq,xx;
struct nod
{
    int x,c;
}q;
vector < nod > a[50001];
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;
    //--n;
    //FA PARCURGERE,NU LUA NODURILE DUPA NUMAR!!!!
    for(i=1;i<n;++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];
            }
        }
    }
    ofstream g("dijkstra.out");
    //++n;
    for(i=2;i<n;++i)g<<v[i]<<" ";
    return 0;
}