#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;
}

void 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;
            }
        }
    }

    ofstream fout("dijkstra.out");
    for (int i = 2; i <= n; i++)
        if(lower_distance[i] == numeric_limits<int>::max())
            fout<<0<<" ";
        else
            fout<<lower_distance[i]<<" ";
    fout.close();
}

void solve(int n, vector<pi> node[])
{
    dijkstra(1, n, node, n);
}

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);
}