// http://infoarena.ro/problema/dijkstra
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define maxSize 50001
#define INFINITY 0x3f3f3f3f
#define cost first
#define location second

int nodes;
vector<int> dist(maxSize,INFINITY);
vector< pair<int,int> > graph[maxSize];
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > myHeap;

void read();
void dijkstra(int startNode);
void write();

int main() {
    read();
    dijkstra(1);
    write();

    return (0);
}

void read() {
    ifstream in("dijkstra.in");
    int edges,from,cost,to;

    in >> nodes >> edges;
    for(int i=1;i<=edges;i++) {
        in >> from >> to >> cost;

        // graful este orientat
        graph[from].push_back(make_pair(cost,to));
    }

    in.close();
}

void dijkstra(int startNode) {
    dist[startNode] = 0;

    pair<int,int> currentNode;
    vector< pair<int,int> >::iterator neighbour;
    vector< pair<int,int> >::iterator end;

    // se introduce nodul de pornire in heap
    myHeap.push(make_pair(0,startNode));

    while(!myHeap.empty()) {
        // se extrage nodul cu costul minim
        currentNode = myHeap.top();

        // se elimina acest nod
        myHeap.pop();

        end = graph[currentNode.location].end();

        // pentru toti vecinii nodului curent
        for(neighbour=graph[currentNode.location].begin();neighbour!=end;++neighbour)
            // daca se poate imbunatatii distanta
            if(dist[neighbour->location] > dist[currentNode.location] + neighbour->cost) {
                // se actualizeaza distanta
                dist[neighbour->location] = dist[currentNode.location] + neighbour->cost;

                // se introduce nodul in heap
                myHeap.push(make_pair(dist[neighbour->location],neighbour->location));
            }
    }
}

void write() {
    ofstream out("dijkstra.out");

    for(int i=2;i<=nodes;i++)
        out << ((dist[i] == INFINITY) ? 0 : dist[i]) << " ";

    out.close();
}