#include <iostream>
#include <fstream>

#define inf 1000000

using namespace std;


struct Drum
{
    int x,y,c;
};

int main()
{
    static Drum a[250001];
    long val[50001];

    ifstream fin("dijkstra.in");
    ofstream g("dijkstra.out");

    int n,m;
    fin >> n >> m ;

    for (int i=0;i<m;i++)
        fin >> a[i].x >>a[i].y >> a[i].c;

    for (int i=1; i<=n;i++)
         val[i]=inf;

        val[1]=0;

    bool ok=true;

    while (ok)
    {
        ok = false;

        for (int i = m-1; i>=0; i--)
       {
           if ((val[a[i].x]+a[i].c) < val[a[i].y] )
           {
               ok = true;
               val[a[i].y] = val[a[i].x] + a[i].c;
           }
       }
    }

    for (int i=2;i<=n;i++)
        if (val[i] != inf)
            g << val[i] << " ";
        else g<< "0 ";

    return 0;
}