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

using namespace std;

#define MAX 50005
#define INF 1005
#define FS first
#define SS second

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

typedef pair < int, int > P ;
vector < P > graph[MAX];
priority_queue< P,  vector < P >, greater<P> > Q; //
int costMin[MAX], N,M;

void readPairs()
{
    fin>>N>>M;
    for (int i=0;i<M;i++)
    {
        int u,v,cost;
        fin>>u>>v>>cost;
        u--; v--;
        graph[u].push_back( P ( cost,v));
    }
}

void dijkstra()
{
    for (int i = 0; i<N; i++) costMin[i] = INF;
    costMin[0] = 0;
    vector < P > :: iterator it;

    Q.push( P ( 0, 0) );
    while  (!Q.empty() )
    {
        P aux = Q.top(); Q.pop();
        for ( it = graph[aux.SS].begin(); it != graph[aux.SS].end(); it++)
            if ( costMin[it->SS] > costMin[aux.SS] + it->FS )
            {
                costMin[it->SS] = costMin[aux.SS] + it->FS;
                Q.push( P( costMin[it->SS], it->SS) );
            }
    }
}

void printAnswer()
{
    for (int i = 1; i<N; i++)
        fout<<((costMin[i] < INF ) ? costMin[i] : 0)<<" ";
}

int main()
{
    if(!fin) return -1;

    readPairs();
    dijkstra();
    printAnswer();

    return 0;
}