#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;

#define INF INT_MAX

struct dist_vecin
{
    int elem, cost;
};

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

    if(!in)
    {
        cout << "eroare";
        return -1;
    }

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

    vector <vector <dist_vecin> > graf(n);
    vector <int> dist(n, INF);
    vector <int> viz(n);

    for(int i = 0; i < m; ++i)
    {
        int a;
        dist_vecin vecin;
        in >> a >> vecin.elem >> vecin.cost;
        vecin.elem--;
        graf[a-1].push_back(vecin);
    }

    dist[0] = 0;

    for(int r = 0; r < n; ++r)
    {
        int ind_min = 0;
        while(viz[ind_min] != 0) ind_min++;
        for(int i = 0; i < n; ++i)
            if(dist[i] < dist[ind_min] && viz[i] == 0)
                ind_min = i;

        //int ind_min = min_element(dist.begin(), dist.end()) - dist.begin();

        for(int j = 0; j < graf[ind_min].size(); ++j)
        {
            dist_vecin aux = graf[ind_min][j];
            if(dist[ind_min] + aux.cost < dist[aux.elem])
                dist[aux.elem] = dist[ind_min] + aux.cost;
        }
        viz[ind_min] = 1;
    }

    for(int i = 1; i < n; ++i)
        out << dist[i] << ' ';

    in.close();
    out.close();
    return 0;
}