#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
//#define fin cin
//#define fout cout
const int nax = 5e4+2;
//const int64_t inf = 1e17;
const int inf = 1e9+2;

int n,m,p;
int y,x,w;

int cmin[nax];

void dijkstra(int node, vector<vector<pair<int,int>>> G){
    bitset<nax> vis;
    vis[node]=true;
    class CompareVf{
    public:
        bool operator () (const int &x,const int &y){
            return cmin[x]>cmin[y];
        }
    };
    memset(cmin,inf,sizeof(cmin));
    cmin[node]=0;
    priority_queue<int, vector<int>, CompareVf> H;
    H.push(node);
    while(!H.empty()){
        int vfMin=H.top();
        H.pop();
        for(pair<int,int> it:G[vfMin]){
            if(cmin[it.first] > cmin[vfMin] + it.second){
                cmin[it.first] =  cmin[vfMin] + it.second;
                vis[it.first]=true;
                H.push(it.first);
            }
        }
    }
}
void afisare(){
    for(int i=2;i<=n;i++)
        fout<<cmin[i]<<' ';
}
int main(){
    fin>>n>>m;
    vector<vector<pair<int,int>>> G(n+1);
    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        G[x].push_back({y,w});
    }
    dijkstra(1,G);
    afisare();
    return 0;
}