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

using namespace std;

const int MAX_SIZE = 50001;
const int oo = 100000000;

typedef pair < int, int > Edge;

class Djikstra
{
    int N;
    int M;

    vector< Edge > myList[MAX_SIZE];
    vector< int  > Solution;
    multiset< Edge > myHeap;

    void Init();
    void ReadData();

public :
    Djikstra();

    void Solve();
    void Print();
};

void Djikstra :: Init()
{
    Solution.resize( N + 1);

    for(int i = 2; i <= N; ++i)
    {
        Solution[i] = oo;
    }

    myHeap.insert( make_pair(0, 1) );
}

void Djikstra :: ReadData()
{
    ifstream in("dijkstra.in");

    in >> N >> M;
    for(int x, y, cost, i = 1; i <= M; ++i)
    {
        in >> x >> y >> cost;
        myList[x].push_back( make_pair(y, cost) );
    }
}

Djikstra :: Djikstra()
{
    ReadData();
    Init();
}

void Djikstra :: Solve()
{
    vector < Edge > :: iterator it;

    while( !myHeap.empty() )
    {
        Edge node = *myHeap.begin();
        myHeap.erase( myHeap.begin() );

        for(it = myList[node.second].begin(); it != myList[node.second].end(); ++it)
        {
            if(Solution[it->first] > it->second + node.first)
            {
                myHeap.erase( make_pair(Solution[it->first], it->first));
                Solution[it->first] = it->second + node.first;
                myHeap.insert( make_pair(Solution[it->first], it->first) );
            }
        }
    }
}

void Djikstra :: Print()
{
    ofstream out("dijkstra.out");

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

int main()
{
    Djikstra Graph;

    Graph.Solve();
    Graph.Print();

    return 0;
}