#include <fstream>

#define N 50001
#define oo 1000000

using namespace std;

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

int a[N][N], n, m;
int d[N]; // d[k]=costul min al unui drum de la nodul p la k
int p; //nodul de start
bool F[N]; // F[k]=1 daca s a determinat costul min pana la k

void Citire()
{
    int x, y, cost;
    fin >> n >> m;
    //initializare matrice ponderi
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= n; j++ )
            if ( i != j ) a[i][j] = oo;
    //completare costuri arce
    while ( fin >> x >> y >> cost )
        a[x][y] = cost;
}

void Dijkstra(int S) //S=nodul de start
{
    int x, dmin;

    //initializare
    for ( int i = 1; i <= n; i++ ) 
        d[i] = a[S][i];

    //nodul de start
    d[S]=0;
    F[S]=1;
    
    //selectem de (n-1) ori cate un nod
    for ( int i = 1; i <= n-1; i++ )
    {
        dmin = oo;
        for ( int j = 1; j <= n; j++ )
            if ( !F[j] && d[j]<dmin )
            {
                dmin = d[j];
                x = j;
            }
        F[x] = 1;

        if ( dmin != oo )
        {
            for ( int j = 1; j <= n; j++ )
                if ( !F[j] && d[x]+a[x][j] < d[j] )
            d[j] = d[x] + a[x][j];
        }
    }
}

void Afisare()
{
    for ( int i = 1; i <= n; i++ )
        if ( d[i] == oo ) fout << -1 << " ";
    else fout << d[i] << " ";
}

int main()
{
    Citire();
    Dijkstra(1);
    Afisare();

    return 0;
}