#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct {int a,b,c;} m[250001];
int n,o,d[50002];
bool k=1;
int main()
{
    f>>o;
    for(int h=2;h<=o;++h)d[h]=20000*50000+1;
    f>>n;
    for(int h=0;h<n;++h)f>>m[h].a>>m[h].b>>m[h].c;
    while(k)
    {
        k=0;
        for(int i=0;i<n;++i)if(d[m[i].b]>d[m[i].a]+m[i].c)
        {
            k=1;
            d[m[i].b]=d[m[i].a]+m[i].c;
        }
    }
    for(int h=2;h<=o;++h)g<<d[h]<<' ';

}