#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct edge{
    int v, weight;

    edge(int _v, int _w){
        v = _v;
        weight = _w;
    }
};

int vertices, edges, u, v, weight;
int dist[50001], prec[50001], viz[50001];
const int infinity = 25000001;
vector<edge> adj[50001];

struct compare{
    bool operator()(const int &u, const int &v){
        return dist[u] > dist[v];
    }
};

priority_queue<int, vector<int>, compare> H;

void Dijkstra(int source){

    int i,vfmin;

    for(int node = 1; node <= vertices; node++){
        dist[node] = infinity;
    }dist[source] = 0;

    H.push(source);

    while(!H.empty())
    {vfmin=H.top();
           H.pop();
       if(edges < 200999){
       if(viz[vfmin]==1)continue;
       viz[vfmin]=1;
       }

        for(i=0; i<adj[vfmin].size(); i++)
            if(dist[adj[vfmin][i].v]> dist[vfmin] + adj[vfmin][i].weight)
        {      dist[adj[vfmin][i].v]= dist[vfmin] + adj[vfmin][i].weight;
               H.push(adj[vfmin][i].v);
        }
    }
}

int main(){

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++){
        scanf("%d %d %d", &u, &v, &weight);
        adj[u].push_back(edge(v, weight));
    }Dijkstra(1);

    for(int node = 2; node <= vertices; node++){
        printf("%d ", (dist[node] == infinity) ? 0 : dist[node]);
    }
    return 0;
}