#include<fstream>
#include<vector>
#include<set>
#include<cstring>
#include<algorithm>

using namespace std;
typedef int var;

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

#define MAXN 100001
#define INF 1000000001

var DIST[MAXN];
struct Node {
    var nod, d;
    Node(var a, var b) {
        nod = a;
        d = b;
    }
};
struct cmp {
    const bool operator()(Node a, Node b) const{
        return a.d < b.d;
    }
};

multiset<Node, cmp> SET;
var n;

struct Edge {
    var n, c;
    Edge(var a, var b) {
        n = a;
        c = b;
    }
};

vector<Edge> G[MAXN];



void dijkstra(var start) {
    fill(DIST+1, DIST+n+1, INF);
    DIST[start] = 0;
    for(var i=1; i<=n; i++) {
        SET.insert(Node(i, DIST[i]));
    }

    while(!SET.empty()) {
        var node = (*(SET.begin())).nod;
        DIST[node] = (*(SET.begin())).d;
        SET.erase(SET.begin());


        for(vector<Edge>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            Edge &e = *it;
            if(DIST[e.n] > DIST[node] + e.c) {
                set<Node>::iterator it2 = SET.find(Node(e.n, DIST[e.n]));
                DIST[e.n] = DIST[node] + e.c;
                SET.erase(it2);
                SET.insert(Node(e.n, DIST[e.n]));
            }
        }
    }
}

int main() {

    var m, a, b, c;
    fin>>n>>m;

    while(m--) {
        fin>>a>>b>>c;
        G[a].push_back(Edge(b, c));
    }

    dijkstra(1);

    for(var i=2; i<=n; i++) {
        fout<<DIST[i]<<" ";
    }

    return 0;
}