#include <cstdio>
#include <cstdlib>
#include <fstream>

#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);
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

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

    solve();

    for (int i = 2; i<=N; i++)
        //printf("%d ", (dmin[i] < INF ) ? dmin[i] : 0);
        fout<<((dmin[i] < INF ) ? dmin[i] : 0)<<" ";

    return 0;
}