#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

int extractMin(int n, bool visited[], int lower_distance[])
{
    int min_distance = numeric_limits<int>::max(), min_index = -1;
    for(int i = 1; i <= n; i++)
    {
        if(lower_distance[i] < min_distance && visited[i] == false)
        {
            min_index = i;
            min_distance = lower_distance[i];
        }
    }

    return min_index;
}

int dijkstra(int s, int f, vector<pi> node[], int n)
{
    bool visited[n+1];
    int lower_distance[n+1];
    int index = -1;

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

    lower_distance[s] = 0;
    while((index = extractMin(n, visited, lower_distance)) != -1)
    {
        visited[index] = true;
        for (auto i = node[index].begin(); i != node[index].end(); ++i)
        {
            int new_distance = lower_distance[index];
            new_distance = new_distance + i->second;
            if(new_distance < lower_distance[i->first])
            {
                lower_distance[i->first] = new_distance;
            }
        }
    }

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

    return lower_distance[f];
}

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

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

    fout.close();
}

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

    fin>>n>>m;

    vector<pi> node[n];

    for(int i = 1; i <= n; i++)
    {
        node[i].clear();
    }

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

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

    fin.close();

    solve(n, node);
}