#include <fstream>
#include <vector>
#include <set>

#define _Pair pair<int, int>
#define Max_Size 50009
#define oo 1000000

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";

int N, M, Distance[Max_Size];

vector < _Pair > Graph[Max_Size];

multiset < _Pair > my_Heap;

inline void Read_Data()
{
ifstream in( iname );

    in >> N >> M;
    for(int x, y, cost, i = 1; i <= M; ++i) {
        in >> x >> y >> cost;

        Graph[x].push_back( {y,cost} );
    }
}


inline void Init()
{
    for(int i = 2; i <= N; ++i) Distance[i] = oo;
    my_Heap.insert( {0, 1} );
}

void Compute()
{
    while(!my_Heap.empty()) {
        _Pair nod = *my_Heap.begin();
        my_Heap.erase( nod );

        for(vector <_Pair > :: iterator it = Graph[nod.second].begin(); it != Graph[nod.second].end(); ++it)
            if(Distance[it->first] > nod.first + it->second)    {
                my_Heap.erase( {Distance[it->first], it->first} );
                Distance[it->first] = nod.first + it->second;
                my_Heap.insert( {Distance[it->first], it->first } );
            }
    }
}

inline void Write()
{
    ofstream out(oname);

    for(int i = 2; i <= N; ++i)     out << (Distance[i] == oo ? 0 : Distance[i]) << ' ';
}

int main()
{
    Read_Data();
    Init();
    Compute();
    Write();

    return 0;
}