#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>
#include <algorithm>
#include <deque>
#include <tuple>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

class Graph {
    std::vector<std::vector<int>> Ad;
    std::vector<std::vector<int>> Cost;
    int nodes; // no of nodes
    int edges; // no of edges
    int directed; // 1 for directed
    const int inf = 100000000;
public:
    Graph();
    Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges,int directed);
    Graph(const std::vector<std::pair<int,int>> &ad, const std::vector<int> &cost, int nodes, int edges,int directed);
    int getComponents();
    void pathTo(int node);
    std::stack<int> topSort();
    void printSCC(); // print strongly connected components
    void printBCC(); //print biconex components
    void printTopSort();
    void disjoint();
    void mst();
    void bellman();
    void dijkstra();

private:
    void DFS(int node, std::vector<int> &vis);
    void BFS(int node, std::vector<int> &vis);
    void topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s);
    void dfsSCC(int node,int &idInc, std::vector<int> &id, std::vector<int> &low, std::vector<bool> &onStack, std::stack<int> &s, std::vector< std::vector<int>> &scc); // dfs for scc
    std::vector< std::vector<int>> getSCC(); // returns scc with tarjan
    void dfsBCC(int node, int parent, int &time, std::vector<int> &dq, std::vector<int> &low, std::vector<int> &disc, std::vector<std::vector<int>> &bcc);
    int Find(int x, std::vector<int> &disjSets);
    void Union(int x, int y, std::vector<int> &disjSets, std::vector<int> &sizes);
    void getDistances(bool &cycle, std::vector<int> &dist);
    void getDistancesDijkstra(std::vector<int> &dist);
};

Graph::Graph(){}

Graph::Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges, int directed) : nodes(nodes), edges(edges), directed(directed) {
    Ad.resize(nodes+1);
    for(int i = 0; i<edges; ++i){
        Ad[ad[i].first].push_back(ad[i].second);
        if(directed == 0)
            Ad[ad[i].second].push_back(ad[i].first);
    }
}

Graph::Graph(const std::vector<std::pair<int,int>> &ad, const std::vector<int> &cost, int nodes, int edges,int directed) : nodes(nodes), edges(edges), directed(directed) {
    Ad.resize(nodes+1);
    Cost.resize(nodes+1);
    for(int i = 0; i<edges; ++i){
        Ad[ad[i].first].push_back(ad[i].second);
        Cost[ad[i].first].push_back(cost[i]);
        if(directed == 0){
            Ad[ad[i].second].push_back(ad[i].first);
            Cost[ad[i].second].push_back(cost[i]);
        }
    }
}

void Graph::DFS(int node, std::vector<int> &vis){
    vis[node] = 1;
    for(int i = 0; i<Ad[node].size(); ++i)
        if(vis[Ad[node][i]] == 0){
            DFS(Ad[node][i], vis);
        }
}

int Graph::getComponents() {
    std::vector<int> vis;
    int ct = 0;
    vis.resize(nodes);
    std::fill(vis.begin(), vis.end(), 0);
    for(int i = 1;i <= nodes; ++i)
        if(vis[i] == 0){
            DFS(i, vis);
            ct++;
        }
    return ct;
}

void Graph::BFS(int node, std::vector<int> &vis){
    int parent, distance;
    std::queue<int> Q;
    Q.push(node);
    vis[node] = 0;
    while(!Q.empty()){
        parent = Q.front();
        Q.pop();
        for(int i = 0; i<Ad[parent].size(); ++i)
            if(vis[Ad[parent][i]] == -1){
                Q.push(Ad[parent][i]);
                vis[Ad[parent][i]] = vis[parent] + 1;
            }
    }
}

void Graph::pathTo(int node){
    std::vector<int> vis;
    vis.resize(nodes+1);
    std::fill(vis.begin(), vis.end(), -1);
    vis[node] = 0;
    BFS(node, vis);
    for(int i = 1; i<= nodes; ++i)
        fout << vis[i]<< " ";
}

void Graph::topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s){
    vis[node] = 1;
    for(int i = 0; i<Ad[node].size(); ++i)
        if(vis[Ad[node][i]] == 0)
            topSortDFS(Ad[node][i], vis, s);
    s.push(node);
}

std::stack<int> Graph::topSort(){
    std::vector<int> vis;
    std::stack<int> s;
    vis.resize(nodes+1);
    std::fill(vis.begin(), vis.end(), 0);
    for(int i = 1; i<=nodes; ++i)
        if(!vis[i])
           topSortDFS(i, vis, s);
    return s;
}

void Graph::printTopSort(){
    std::stack<int> s; //topsort stack
    s = topSort();
        while(!s.empty()){
        fout << s.top() << " ";
        s.pop();
    }
}

void HavelHakimi(){
    int cSort[1005] = {0};
    int maxim;
    std::vector<int> v;
    int n,x, val; // val - deleted value in havel hakimi
    bool hh = true; //check if havel hakimi conditions are still met
    fin >> n;
    cout << n;
    for(int i = 0; i<n; ++i){
        fin >> x;
        cSort[x]++;
        if(x > maxim)
            maxim = x;
        v.push_back(x);
    }
    while(true){
        if(maxim == 0)
            break;
        cSort[maxim]--; //extract max
        val = maxim;
        n--;
        if(n < val){
            hh = false;
            break;
        }
        while(maxim > 0 && val > 0){
            cSort[maxim]--;
            cSort[maxim-1]++;
            val--;
            if(cSort[maxim] == 0)
                maxim--;

        }
        if(maxim == 0 && val > 0){
            hh = false;
            break;
        }
    }
    if( hh == true )
        std::cout << "Simple graph.";
    else std::cout << "Not a simple graph.";
}

int Graph::Find(int x, std::vector<int> &disjSets){
    int root = x, aux;
    while(disjSets[root] != root)
        root = disjSets[root];
    while(disjSets[x] != root){
        aux = disjSets[x];
        disjSets[x] = root;
        x = aux;
    }
    return root;
}

void Graph::Union(int x, int y, std::vector<int> &disjSets, std::vector<int> &sizes){
    int rootx = Find(x, disjSets);
    int rooty = Find(y, disjSets);
    if(sizes[rootx] >= sizes[rooty]){
        sizes[rootx] += sizes[rooty];
        disjSets[rooty] = rootx;
    }
    else{
        sizes[rooty] += sizes[rootx];
        disjSets[rootx] = rooty;
    }
}

void Graph::disjoint(){
    std::vector<int> disjSets, sizes; //vectors for disjoint sets and their respective sizes
    int n,m,x,y,op;
    fin >> n >> m;
    disjSets.push_back(0);
    sizes.push_back(0);
    for(int i = 1; i<=n; ++i){
        disjSets.push_back(i);
        sizes.push_back(1);
    }
    for(int i = 1; i<=m; ++i){
        fin >> op >> x >> y;
         if(op == 1){
            if(Find(x, disjSets) != Find(y, disjSets))
                Union(x, y, disjSets, sizes);
        }
        else{
            if(Find(x, disjSets) != Find(y, disjSets))
                fout << "NU\n";
            else fout << "DA\n";
        }
    }
}

void Graph::mst(){
    std::vector< tuple<int, int, int> > edges;
    std::vector<int> disjSets, sizes; //vectors for disjoint sets and their respective sizes
    std::vector<int> sol;
    int solSize = 0, cost = 0;
    int n,m,x,y,c;
    fin >> n >> m;
    //initialize disjSet and size
    disjSets.push_back(0);
    sizes.push_back(0);
    for(int i = 1; i<=n; ++i){
        disjSets.push_back(i);
        sizes.push_back(1);
    }

    for(int i = 1; i<=m; ++i){
        fin >> x >> y >> c;
        edges.push_back( std::make_tuple(c, x, y) );
    }
    sort(edges.begin(), edges.end());
    for(int i = 0; i<m && solSize < n-1; ++i){
        x = get<1>(edges[i]);
        y = get<2>(edges[i]);
        if( Find(x,disjSets) != Find(y, disjSets) ){
            Union(x,y, disjSets, sizes);
            cost += get<0>(edges[i]);
            sol.push_back(i);
            ++solSize;
        }
    }
    fout << cost << "\n" << solSize << "\n";
    for(int i = 0; i<solSize; ++i){
        int j = sol[i];
        fout << get<1>(edges[j]) << " " << get<2>(edges[j])<< "\n";
    }
}

void Graph::dfsSCC(int node,int &idInc, std::vector<int> &id, std::vector<int> &low, std::vector<bool> &onStack, std::stack<int> &s, std::vector< std::vector<int>> &scc){
    int nod;
    s.push(node);
    onStack[node] = true;
    id[node] = low[node] = idInc++;
    for(int i = 0; i<Ad[node].size(); ++i){
        int next = Ad[node][i];
        if(id[next] == 0)
            dfsSCC(next, idInc, id, low, onStack, s, scc);
        if(onStack[next] == true)
            low[node] = min(low[node], low[next]);
    }
    if(id[node] == low[node]){
        std::vector<int> comp; ///next component in scc vector
        while(!s.empty()){
            nod = s.top();
            s.pop();
            onStack[nod] = false;
            comp.push_back(nod);
            low[nod] = id[node];
            if(nod == node)
                break;
        }
        scc.push_back(comp);
    }
}

std::vector< std::vector<int>> Graph::getSCC(){
    int idInc = 1; //increment node id
    std::vector<int> id(nodes+1);
    std::vector<int> low(nodes+1);
    std::vector<bool> onStack(nodes+1, 0);
    std::vector< std::vector<int>> scc; //vector of components
    std::stack<int> s;
    for(int i = 1; i<=nodes; ++i)
        id[i] = low[i] = 0;
    for(int i = 1; i<=nodes; ++i)
        if(id[i] == 0)
            dfsSCC(i,idInc, id, low, onStack, s, scc);
    return scc;
}

void Graph::printSCC(){
    std::vector< std::vector<int>> scc;
    scc = getSCC();
    fout << scc.size() << "\n";
    for(int i = 0; i<scc.size(); ++i){
        for(int j = 0; j<scc[i].size(); ++j)
            fout << scc[i][j] << " ";
        fout << "\n";
    }
}

void Graph::dfsBCC(int node, int parent, int &time, std::vector<int> &dq, std::vector<int> &low, std::vector<int> &disc, std::vector<std::vector<int>> &bcc){
    int w;
    disc[node] = low[node] = ++time;
    for(int i = 0; i<Ad[node].size(); ++i){

        w = Ad[node][i];

        if(w == parent)
            continue;

        if(disc[w] != 0)
            low[node] = min(low[node], disc[w]);

        else{
            dq.push_back(w);
            dfsBCC(w, node, time, dq, low, disc, bcc);

            low[node] = min(low[w], low[node]);

            if(low[w] >= disc[node]){
                dq.push_back(node);
                std::vector<int> nextComp;
                while(!dq.empty()){
                    int next = dq.back();
                    dq.pop_back();
                    nextComp.push_back(next);
                    if(next == w)
                        break;
                }
                bcc.push_back(nextComp);
            }
        }
    }

}

void Graph::printBCC(){
    int time = 0;
    std::vector<std::vector<int>> bcc;
    std::vector<int> dq; ///deque for components in next bcc
    std::vector<int> low(nodes), disc(nodes);
    dfsBCC(1,0,time, dq, low, disc, bcc);
    fout << bcc.size() << "\n";
    for(int i = 0; i<bcc.size(); ++i){
        for(int j = 0; j<bcc[i].size(); ++j)
            fout << bcc[i][j] << " ";
        fout << "\n";
    }
}

void Graph::getDistances(bool &cycle, std::vector<int> &dist){
    std::vector<int> countQ(nodes+1, 0); //number of times a node has been added to queue
    std::vector<bool> inQ(nodes+1, 0); //node in queue

    deque<int> q;
    int currentNode;
    int w,c;
    q.push_back(1);
    while( !q.empty() && !cycle ){
        currentNode = q.front();
        q.pop_front();
        inQ[currentNode] = 0;

        for(int i = 0; i<Ad[currentNode].size(); ++i){
            w = Ad[currentNode][i];
            c = Cost[currentNode][i];
            if( dist[w] > dist[currentNode] + c ){
                dist[w] = dist[currentNode] + c;
                //cout << currentNode << " " << w << " " << dist[w] << " " << c << "\n";
                if( !inQ[w] ){
                    if( countQ[w] > nodes ){ //if node has updated the distance more than n times, this means it's part of a negative cycle
                        cycle = 1;
                        break;
                    }
                    else{
                        inQ[w] = 1;
                        countQ[w]++;
                        q.push_back(w);
                    }
                }
            }
        }
    }
}

void Graph::bellman(){
    bool cycle = false;
    std::vector<int> dist; //distance vector;
    dist.resize(nodes+1, inf);
    dist[1] = 0;
    getDistances(cycle, dist);
    if(cycle)
        fout << "Ciclu negativ!\n";
    else{
        for(int i=2; i<=nodes; i++)
            fout<<dist[i]<<" ";
        fout<<'\n';
    }

}

void Graph::getDistancesDijkstra(std::vector<int> &dist){
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
    std::vector<bool>inH(nodes+1, 0);
    int currentNode, w, c;
    heap.push({0,1});

    while(!heap.empty()){
        currentNode = heap.top().second;
        heap.pop();
        if(inH[currentNode])
            continue;
        else inH[currentNode] = true;

        for(int i = 0; i < Ad[currentNode].size(); ++i){
            w = Ad[currentNode][i];

            if( dist[currentNode] + Cost[currentNode][i] < dist[w] ){
                dist[w] = dist[currentNode] + Cost[currentNode][i];
                heap.push({ dist[w], w });
            }
        }
    }
}

void Graph::dijkstra(){
    std::vector<int> dist; //distance vector;
    dist.resize(nodes+1, inf);
    dist[1] = 0;
    getDistancesDijkstra(dist);
    for(int i = 2; i<=nodes; ++i)
        if( dist[i] == inf )
            fout << 0 << " ";
        else fout << dist[i] << " ";
}


int main() {
    std::vector<std::pair<int,int>> Ad;
    std::vector<int> Cost;
    int n,m,x,y,c;
    fin >> n >> m;
    for(int i = 0; i<m; ++i){
        fin >> x >> y >> c;
        Ad.push_back({x,y});
        Cost.push_back(c);
    }
    Graph G(Ad, Cost, n ,m, 1);
    G.dijkstra();
    return 0;
}