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

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

list<Node> adj[50001];
vector<long> dist;
vector<bool> vis;
int n,m,a,b,c;

int getBestNode(){
    int bestIndex=0;
    long min0=LONG_MAX;
    for(int i=1;i<=n;i+=1){
        if(dist[i]<min0&&!vis[i]){
            bestIndex=i;
            min0=dist[i];
        }
    }
    return bestIndex;
}

int main()
{
    fin>>n>>m;
    dist.resize(n+1);
    fill(dist.begin(),dist.end(),LONG_MAX);
    vis.resize(n+1);
    fill(vis.begin(),vis.end(),false);
    for(int i=0;i<m;i+=1){
        fin>>a>>b>>c;
        adj[a].push_back(Node(b,c));
    }
    fin.close();
    dist[1]=0;
    for(int i=1;i<=n;i+=1){
        int nextStep=getBestNode();
        vis[nextStep]=true;
        for(list<Node>::iterator it=adj[nextStep].begin();it!=adj[nextStep].end();it++){
            if(dist[it->vecin]>dist[nextStep]+it->cost)
                dist[it->vecin]=dist[nextStep]+it->cost;
        }
    }
    for(int i=2;i<=n;i+=1)
        if(dist[i]!=LONG_MAX)
            fout<<dist[i]<<' ';
        else
            fout<<0<<' ';
    return 0;
}