//
//  main.cpp
//  Dijkstra
//
//  Created by Andu Andu on 11/11/2019.
//  Copyright © 2019 Andu Andu. All rights reserved.
//

#include <fstream>
#include <vector>
#include <queue>
#define N 10000000
#define INF 10000000

using namespace std;

ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");

class Graph {
private:
    vector<int> nodesdad;
    vector<int> nodechildren;
    vector<int> cost;
public:
    Graph(int);
    vector<int> nodes;
    void addNodes(int ,int ,int );
    vector<pair<int,int>> gasesteVeciniNeorientat(int);
    vector<pair<int,int>> gasesteVeciniOrientat(int);
    int returnCost(int,int);
};
Graph::Graph(int nrnodes) {
    for (int i=1;i<=nrnodes;i++) {
        this->nodes.push_back(i);
    }
}
int Graph::returnCost(int node1, int node2) {
    for (int i=0;i<=this->nodesdad.size() - 1;i++) {
        if ((this->nodesdad[i] == node1 and this->nodechildren[i] == node2) or (this->nodesdad[i] == node2 and this->nodechildren[i] == node1)) {
            return this->cost[i];
        }
    }
    return 0;
}

void Graph::addNodes(int node1, int node2, int cost) {
    this->nodesdad.push_back(node1);
    this->nodechildren.push_back(node2);
    this->cost.push_back(cost);
}

vector<pair<int,int>> Graph::gasesteVeciniNeorientat(int node) {
    vector<pair<int,int>> vecini;
    for (int i=0;i<nodesdad.size();i++ ) {
        if (nodesdad[i] == node)
            vecini.push_back({this->nodechildren[i], this->cost[i]});
    }
    for (int i=0;i<nodechildren.size();i++ ) {
        if (nodechildren[i] == node)
            vecini.push_back({this->nodesdad[i], this->cost[i]});
    }
    return vecini;
}

vector<pair<int,int>> Graph::gasesteVeciniOrientat(int node) {
    vector<pair<int,int>> vecini;
    for (int i=0;i<nodesdad.size();i++ ) {
        if (nodesdad[i] == node)
            vecini.push_back({this->nodechildren[i], this->cost[i]});
    }
    return vecini;
}


int dist[N];
struct compare
{
    bool operator()(const int& l, const int& r)
    {
        return dist[l] > dist[r];
    }
};
priority_queue<int, vector<int>, compare> Q;
void Dijkstra(Graph graph, int source) {
    dist[source] = 0;
    for( auto node: graph.nodes ) {
        if (node != source)
            dist[node] = INF;
        Q.push(node);
    }
    dist[source] = 0;
    while ( !Q.empty() ) {
        int min = 999;
        int index = -1;
        int v = Q.top();
        Q.pop(); // pt ca e priority qiu
        for ( auto neigbour: graph.gasesteVeciniNeorientat(v) ) {
            int neighbour = neigbour.first;
            int alt = dist[v] + graph.returnCost(v, neighbour);
            if (alt < dist[neighbour]) {
                dist[neighbour] = alt;
            }
        }
        
    }
}

int n,a,b,c,sursa;

int main() {
    cin>>sursa>>n;
    Graph graph = Graph(sursa);
    for(int i=1;i<=n;i++) {
        cin>>a>>b>>c;
        graph.addNodes(a, b, c);
    }
    Dijkstra(graph, 1);
    for (int i=2;i<=graph.nodes.size();i++) {
        cout<<dist[i]<<" ";
    }
    return 0;
}
/*
 5 6
 1 2 1
 1 4 2
 4 3 4
 2 3 2
 4 5 3
 3 5 6
 */