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

#define MaxN 50009
#define oo 1000000
#define POINT pair<long long, long long>

using namespace std;

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

class DijkstraAlgorithm
{
    protected :
        int N, M;
        vector <POINT> Graph[MaxN];
        long long Distance[MaxN];
        multiset < POINT > my_Heap;

    public :
        void ReadData()
        {
            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} );
            }
        }

        void Compute()
        {
            //while(!my_Heap.empty()) my_Heap.erase( *my_Heap.begin() );
            for(int i = 2; i <= N; ++i) Distance[i] = oo;

            Distance[1] = 0;
            my_Heap.insert( {0, 1} );

            while( !my_Heap.empty())    {
                POINT nod = *my_Heap.begin();
                my_Heap.erase( nod );

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

        void WriteData()
        {
            ofstream out( oname );

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

int main()
{
    DijkstraAlgorithm obj;

    obj.ReadData();
    obj.Compute();
    obj.WriteData();

    return 0;
}