#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct Edge{
    int vecin;
    int cost;

    Edge(int vecin,int cost){
        this->vecin=vecin;
        this->cost=cost;
    }
};

struct Node{
    int node;
    int dist;

    Node(int node, int dist){
        this->node=node;
        this->dist=dist;
    }

    bool operator<(const Node &other) const {
        return this->dist > other.dist;
    }
};

list<Edge> adj[50001];
vector<long> dist;
priority_queue<Node> nextStep;
int n,m,a,b,c;

int main()
{
    fin>>n>>m;
    dist.resize(n+1);
    fill(dist.begin(),dist.end(),LONG_MAX);
    for(int i=0;i<m;i+=1){
        fin>>a>>b>>c;
        adj[a].push_back(Edge(b,c));
    }
    fin.close();
    dist[1]=0;
    nextStep.push(Node(1,0));
    while(!nextStep.empty()){
        int x = nextStep.top().node;
        nextStep.pop();
        for(list<Edge>::iterator it=adj[x].begin();it!=adj[x].end();it++){
            if(dist[it->vecin]>dist[x]+it->cost){
                dist[it->vecin]=dist[x]+it->cost;
                nextStep.push(Node(it->vecin,dist[it->vecin]));
            }
        }
    }
    for(int i=2;i<=n;i+=1)
        fout<<(dist[i]==LONG_MAX ? 0:dist[i])<<' ';
    return 0;
}