#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N = 50000, INF = 1 << 30;
int d[N];

struct edge{
    int dest, dist;
};

class cmp
{
  public:
    bool operator() ( edge a, edge b ){
      return a.dist > b.dist;
    }
};

vector <edge> g[N];
priority_queue <edge, vector<edge>, cmp> q;

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        in >> a >> b >> c;
        g[a].push_back(edge{b, c});
    }
    for(int i = 1; i <= n; i++){
        d[i] = INF;
    }
    q.push(edge{1, 0});
    while(!q.empty()){
        edge t = q.top();
        q.pop();
        if(d[t.dest] == INF){
            d[t.dest] = t.dist;
            for(auto it : g[t.dest]){
                q.push(edge{it.dest, it.dist + t.dist});
            }
        }
    }

    for(int i = 2; i <= n; i++){
        if(d[i] == INF){
            out << 0 << " ";
        }
        else{
            out << d[i] << " ";
        }
    }

    return 0;
}