#include <cstdio>
#include <cstdlib>

#include <queue>
#include <vector>

using namespace std;

typedef pair < int, int > P ;

#define MAX 50005
#define INF 0x3f3f3f3f

vector < P > G[MAX];
priority_queue< P,  vector < P >, greater<P> > Q;
int dmin[MAX], N,M;

void solve()
{
    for (int i = 1; i<=N; i++)
        dmin[i] = INF;
    dmin[1] = 0;

    Q.push( P ( 0, 1) );

    while  (!Q.empty() )
    {
        P aux = Q.top(); Q.pop();

        for ( vector < P > :: iterator it = G[aux.second].begin(); it != G[aux.second].end(); it++)
            if ( dmin[it->second] > dmin[aux.second] + it->first )
            {
                dmin[it->second] = dmin[aux.second] + it->first;
                Q.push( P( dmin[it->second], it->second) );
            }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for ( ; M> 0; M--)
    {
        int a,b,c;
        scanf("%d %d %d\n", &a, &b, &c);
        G[a].push_back( P ( c,b));
    }

    solve();

    for (int i = 2; i<=N; i++)
        printf("%d ", dmin[i]);

    return 0;
}