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

using namespace std;

#define MAX 50005
#define INF 1005


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;

class dijkstraSP
{
public:
    void initializer() {for (int i = 0; i<N; i++) costMin[i] = INF; costMin[0] = 0;}
    void setShorthestPath();
};

void dijkstraSP::setShorthestPath()
{

    vector < P > :: iterator it;

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

void read()
{
    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 print()
{
    for (int i = 1; i<N; i++) fout<<((costMin[i] < INF ) ? costMin[i] : 0)<<" ";
}

int main()
{
    if(!fin) {return -1;}
    read();
    dijkstraSP a1;
    a1.initializer();
    a1.setShorthestPath();
    print();

    return 0;
}