#include <fstream>
#include <set>
#include <list>

using namespace std;

list<pair<unsigned short int, unsigned int> > * adjlist;
int * dist;
unsigned short int n;

void rd()
{
    ifstream fin("dijkstra.in");
    unsigned short int i, j;
    unsigned int c;
    fin >> n >> i;
    dist = new int[n + 1];
    adjlist = new list<pair<unsigned short int, unsigned int> >[n + 1];
    while(fin >> i >> j >> c){
        adjlist[i].push_back(make_pair(j, c));
    }
    for(i = 0; i <= n; i++){
        dist[i] = -1;
    }
}

void dijkstra(unsigned short int src)
{
    set<pair<unsigned int, unsigned short int> > pq;
    bool * visited = new bool[n + 1]();
    unsigned int altdist;
    dist[src] = 0;
    pq.insert(make_pair(0, src));
    while(!pq.empty()){
        src = pq.begin() -> second;
        pq.erase(pq.begin());
        for(list<pair<unsigned short int, unsigned int> >::iterator it = adjlist[src].begin(); it != adjlist[src].end(); it++){
            if(!visited[it -> first]){
                if(dist[it -> first] == -1){
                    dist[it -> first] = dist[src] + it -> second;
                } else {
                    altdist = dist[src] + it -> second;
                    if(dist[it -> first] > altdist){
                        dist[it -> first] = altdist;
                    }
                }
                pq.insert(make_pair(dist[it -> first], it -> first));
            }
        }
        visited[src] = true;
    }
    delete[] visited;
}

int main()
{
    ofstream fout("dijkstra.out");
    rd();
    dijkstra(1);
    for(unsigned short int i = 2; i <= n; i++){
        if(dist[i] == -1){
            fout << 0 << " ";
        } else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}