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

#define infile "dijkstra.in"
#define outfile "dijkstra.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

struct edge{
    int key;
    int weight;
};

struct compare{
    inline bool operator() (edge x, edge y) {
        return x.weight < y.weight;
    }
};

const int inf = 1000000;

int n, m;
int x, y, weight;
vector<edge> graph[50005];
multiset<edge, compare> q;

bool vis[50005];
int dist[50005];

void Dijkstra()
{
    for(int i=0; i<=n; i++) dist[i] = inf;
    memset(vis, false, sizeof(vis));
    dist[1] = 0;

    for(q.insert({1, 0}); !q.empty(); q.erase(q.begin())){
        edge now = *q.begin();
        for(unsigned int i=0; i<graph[now.key].size(); i++){
            if(dist[graph[now.key][i].key] > dist[now.key] + graph[now.key][i].weight){
                dist[graph[now.key][i].key] = dist[now.key] + graph[now.key][i].weight;
                q.insert({graph[now.key][i].key, dist[graph[now.key][i].key]});
            }
        }
    }

}


int main()
{
    in >> n >> m;

    for(int i=0; i<m; i++){
        in >> x >> y >> weight;
        graph[x].push_back({y, weight});
    }

    Dijkstra();

    for(int i=2; i<=n; i++){
        if(dist[i] == inf){
            out << '0' << ' ';
        }else{
            out << dist[i] << ' ';
        }
    }

    return 0;
}