#include <iostream>
#include <fstream>
#include <conio.h>

#define inf 1000000
using namespace std;


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

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

    ifstream fin("djikstra.in");
    ofstream fout("djikstra.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++)
        cout << val[i] << " ";



    for (int i=2;i<=n;i++)
        fout << val[i] << " ";

    return 0;
}