#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

#define NMAX 100000
#define INF 2000000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

bitset <NMAX> in_q, ap;
priority_queue <pair <int, int> >q;
vector <pair <int, int> > v[NMAX];

void dijkstra(int source, int n){

    int dist[NMAX];

    for (int i = 1; i <= n; i++)
        in_q[i] =  0,
        dist[i] = INF;

    dist[source] = 0;
    in_q[source] = 1;
    q.push(make_pair(0, source));

    while (!q.empty()){

        int node = q.top().second;
        in_q[node] = 0;
        q.pop();

        for (auto it : v[node])
        if (dist[it.first] > dist[node] + it.second){
            dist[it.first] = dist[node] + it.second;

            if (!in_q[it.first])
                q.push(make_pair(-dist[it.first], it.first));

            in_q[it.first] = 1;

        }
    }

    for (int i = 2; i <= n; i++)
        g << dist[i] << " ";
    g << '\n';

    return;
}

inline void dfs(int node){

    ap[node] = 1;
    for (auto it : v[node])
        if (!ap[it.first])
            dfs(it.first);

    g << node << " ";
}

int main(){

    int n, m, x, y, z;

    f >> n  >> m;

    for (int i = 1; i <= m; i++){

        f >> x >> y >> z;

        v[x].push_back(make_pair(y, z));
        //v[y].push_back(make_pair(x, z));

    }

    //dfs(1);
    dijkstra(1, n);

    f.close();
    g.close();

    return 0;
}