#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair

using namespace std;

const int NMAX = 50001;
const int oo = 100000000;
typedef pair<int, int> Edge;

class Dijkstra
{
    int N, M;
    vector<Edge> myList[NMAX];
    vector<int> Solution;
    multiset<Edge> myHeap;

    void Init();
    void ReadData();
public:
    Dijkstra();
    void Solve();
    void Print();

};

void Dijkstra :: 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) );
    }
}

void Dijkstra::Init()
{
    Solution.resize(N+1);
    for(int i = 2; i <= N; i++)
    {
        Solution[i] = oo;
    }
    myHeap.insert(mp(0, 1)); // cost 0 nod 1
}

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

void Dijkstra::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 Dijkstra :: Print()
{
    ofstream out("dijkstra.out");

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

int main()
{
    Dijkstra Graph;
    Graph.Solve();
    Graph.Print();
    return 0;
}