#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

int dijkstra(int s, int f, vector<pi> graf[], bool visited[], int costs[])
{
    priority_queue<pi, vector<pi>, greater<pi>> queue;

    queue.push(make_pair(0, s));
    visited[s] = true;

    while(!queue.empty())
    {
        pi que_elem = queue.top();
        queue.pop();

        if(graf[que_elem.second].size() <= 0)
        {
            continue;
        }

        for (auto i = graf[que_elem.second].begin(); i != graf[que_elem.second].end(); ++i)
        {
            int new_cost = que_elem.first;

            new_cost += (*i).second;

            if(costs[(*i).first] > new_cost)
            {
                costs[(*i).first] = new_cost;
            }

            if(visited[(*i).first] == false)
            {
                queue.push(make_pair(costs[(*i).first], (*i).first));
                visited[(*i).first] = true;
            }
        }
    }

    if(costs[f] == numeric_limits<int>::max())
    {
        return 0;
    }

    return costs[f];
}

void solve(int n, vector<pi> graf[], bool visited[], int costs[])
{
    ofstream fout("dijkstra.out");

    for (int i = 2; i <= n; i++)
    {
        fout<<dijkstra(1, i, graf, visited, costs)<<" ";
    }

    fout.close();
}

int main()
{
    int n, m;
    ifstream fin("dijkstra.in");

    fin>>n>>m;

    vector<pi> graf[n];
    bool visited[n];
    int costs[n];

    for(int i = 1; i <= n; i++)
    {
        visited[i] = false;
        costs[i] = numeric_limits<int>::max();
        graf[i].clear();
    }

    for(int i = 0; i < m; i++)
    {
        int from, to, cost;
        fin>>from>>to>>cost;

        graf[from].push_back(make_pair(to, cost));
    }

    fin.close();

    solve(n, graf, visited, costs);
}