#include <iostream>
#include <fstream>
#include <climits>
#include <vector>

using namespace std;

#define MAX_NODES 50005
#define INFINITY INT_MAX

struct edge {
    int toNode, dist;
};

int Nodes, numEdges;
vector<edge> Edges[MAX_NODES];

int t[MAX_NODES];
vector<int> G;
bool inG[MAX_NODES];

void InitDijkstra() {
    t[1] = 0;
    G.push_back(1);
    inG[1] = true;

    for (int i = 2; i <= Nodes; ++i)
        t[i] = INFINITY;
}

void DijkstrasAlgorithm() {
    InitDijkstra();

    int yStar, Min;
    for (int i = 2; i <= Nodes; i++) {
        Min = INFINITY;
        for (int markedNode : G) {
            for (edge e : Edges[markedNode]) {
                if ( !inG[e.toNode] ) {
                    if ( t[markedNode] + e.dist < Min ) {
                        yStar = e.toNode;
                        Min = t[markedNode] + e.dist;
                    }
                }
            }
        }

        if (Min == INFINITY)
            break;

        //cout << "Pas " << i << ": " << "y*=" << yStar << " " << "t(y*)=" << Min << "\n";

        t[yStar] = Min;
        G.push_back(yStar);
        inG[yStar] = true;
    }
}

void Read() {
    ifstream fin("dijkstra.in");
    fin >> Nodes >> numEdges;

    int fromNode, toNode, dist;
    for (int i = 0; i < numEdges; ++i) {
        fin >> fromNode >> toNode >> dist;
        Edges[fromNode].push_back( {toNode, dist} );
    }
    fin.close();
}

void Write() {
    ofstream fout("dijkstra.out");
    for (int i = 2; i <= Nodes; ++i)
        if (t[i] != INFINITY)
            fout << t[i] << " ";
        else
            fout << "0 ";
    fout.close();
}

int main()
{
    Read();
    DijkstrasAlgorithm();
    Write();
    return 0;
}