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

#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define inf 0xf3f3f3f

using namespace std;

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

struct edge{
    int key;
    int weight;
};

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

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

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

void Dijkstra()
{
    memset(dist, inf, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[1] = 0;
    vis[1] = true;

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

}


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;
}