#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX 2147483647
int n,m,v[50001],i,x,y,z,j,k;//,l[50001];
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;
    for(i=1;i<n;++i)
    {
        k=a[i].size();//cout<<k<<" ";
        for(j=0;j<k;++j)
        {
            if(a[i][j].c+v[i]<v[a[i][j].x])
            {
                v[a[i][j].x]=a[i][j].c+v[i];
            }
        }
    }
    ofstream g("dijkstra.out");
    ++n;
    for(i=2;i<n;++i)g<<v[i]<<" ";
    return 0;
}