#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],d[100],s[100],p[100],n;
int m;
int const MAX = 5000;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
void init()
{
    in >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <=n; ++j)
            a[i][j] = MAX;
}
void citire()
{
    int i,j,c;
    while(in >> i >> j >> c)
    {
        a[i][j] = c;
    }
}


void generare_drum(int x)
{
    int i,j,min,y;
    s[x] = 1;
    for(i = 1; i <= n; ++i)
    {
        d[i] = a[x][i];
        if(i!=x && d[i] < MAX) p[i] = x;
    }
    for(i = 1; i <= n-1; ++i)
    {
        for(j = 1,min = MAX; j <= n; ++j)
        {
            if(s[j] == 0 && d[j] < min) {min = d[j]; y=j;}
        }
            s[y] = 1;
         for(j = 1; j <= n; ++j)
        if(s[j] == 0 && d[j] > d[y] + a[y][j])
                {
                    d[j] = d[y] + a[y][j];
                    p[j] = y;
                }


    }
}


void drum(int i)
{
    if(p[i] != 0)
        drum(p[i]);
}




int main()
{
    init();
    citire();
    generare_drum(1);
     for(int i = 1; i <= n; ++i)
        if(i != 1)
            if(p[i] != 0)
            {
                out << d[i] << " ";
            }
            else
                out << "-1 ";
    return 0;
}