#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstring>

using namespace std;

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define l 104*10
#define pb push_back
#define DIM 50003

int x , y , v , n , p , m , poz;
int cost[50003];

vector<int>G[50003];
vector<int>C[50003];
char buf[DIM];
queue<int>Q;

int scan()
{
    //char buf[DIM];
    int x = 0;
    while(buf[poz] < '0' || buf[poz] > '9')
        if(++poz == DIM)
            fread(buf, 1, DIM, stdin), poz = 0;
    while(buf[poz] >= '0' && buf[poz] <= '9')
    {
        x = x*10 + (buf[poz]-'0');
        if(++poz == DIM)
            fread(buf, 1, DIM, stdin), poz = 0;
    }
        return x;
}

void Read()
{
    int i;

    scanf ( "%d%d" , &n , &m );

    for ( i = 1 ; i <= m ; i ++ ){
            x = scan();
            y = scan();
            v = scan();

            G[x].pb(y);
            C[x].pb(v);
    }

}

void Solve()
{
    int i;

    cost[1] = 1;

    Q.push(1);

    while (!Q.empty())
    {
        x = Q.front();

        for ( i = 0 ; i < G[x].size() ; i ++ )
            if ( cost[G[x][i]] == 0 or cost[G[x][i]] > cost[x] + C[x][i] )
        {
            cost[G[x][i]] = cost[x]+C[x][i];
            Q.push(G[x][i]);
        }

        Q.pop();
    }

    for ( i = 2 ; i <= n ; i ++ )
        if ( cost[i] == 0 )
            printf ("0 ");
        else
        printf ( "%d " , cost[i]-1 );
}

int main()
{
    freopen (IN,"r",stdin);
    freopen (OUT,"w",stdout);

    Read();
    Solve();
}