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

#define INF 20000

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);
    priority_queue < pair<int, int> > coada;

    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;
    coada.push(make_pair(0, 0));

    while(!coada.empty())
    {
        int ind_min = coada.top().second;
        coada.pop();

        //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(viz[aux.elem] == 0)
            {
                if(dist[ind_min] + aux.cost < dist[aux.elem])
                    dist[aux.elem] = dist[ind_min] + aux.cost;
                coada.push(make_pair(-aux.cost, aux.elem));
            }
        }
        viz[ind_min] = 1;
    }

    for(int i = 1; i < n; ++i)
    {
        if(dist[i] == INF)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    }

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