#include <iostream>
#include <fstream>

using namespace std;

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

int a[50001][5001], n,m,i,j,c;
int d[50001], s[50001], t[50001], minim, poz, Max=1000000;
int main () {
    in>>n>>m;
    for (i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i==j)
                a[i][j] = 0;
            else
                a[i][j] = Max;
    while (in>>i>>j>>c)
    {
        a[i][j] = c;
    }
    s[1] = 1;
    for (i=1; i<=n; i++) {
        d[i] = a[1][i];
        if (i!=1)
            if (d[i]<Max)
                t[i] = 1;
    }
    for (i=1; i<=n-1; i++) {
        minim = Max;
        for (j=1; j<=n; j++)
            if (s[j]==0)
                if (d[j] < minim) {

                    minim = d[j];
                    poz = j;
                }
        s[poz] = 1;
        for (j=1; j<=n; j++)
            if (s[j]==0)
                if (d[j] > d[poz]+a[poz][j]) {
                        d[j] = d[poz] + a[poz][j];
                        t[j] = poz;
                }
    }
    for (i=2; i<=n; i++)
        if (d[i]<1000000)
            out<<d[i]<<" ";
        else
            out<<-1<<" ";
        return 0;
}