#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct comparator
{
 bool operator()(pair<int, int> x, pair<int, int> y)
 {
    return x.second > y.second;
 }
};

const int INFINIT = 1 << 30;
const int MAX_N = 50001;

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int n, m;
    in >> n >> m;

    vector< vector<pair<int, int> > > graph(n);

    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        x--, y--;
        graph[x].push_back(make_pair(y, c));
    }

    vector<int> costs(n, INFINIT);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int> >, comparator> heap;

    costs[0] = 0;
    heap.push(make_pair(0, costs[0]));

    while (!heap.empty())
    {
        int elem = heap.top().first;
        int dist = heap.top().second;
        heap.pop();

        if (!visited[elem])
        {
            visited[elem] = true;
            for (int i = 0; i < graph[elem].size(); i++)
            {
                if (!visited[graph[elem][i].first] && (graph[elem][i].second + dist < costs[graph[elem][i].first]))
                {
                    costs[graph[elem][i].first] = graph[elem][i].second + dist;
                    heap.push(make_pair(graph[elem][i].first, costs[graph[elem][i].first]));
                }

            }
        }
    }

    for (int i = 1; i < n; i++)
        if (costs[i] == INFINIT)
            out << 0 << " ";
        else
            out << costs[i] << " ";


    return 0;
}