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

using namespace std;

const int maxm=1e9;
int n, m, t[50001];
bool ct[50001];

vector<pair<int, int> >v[50001];
priority_queue<pair<int, int> >h;
int main() {
    int x, y, c, i, nod, newn, cost;

    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(i=0;i<m;i++) {
        fin>>x>>y>>c;
            v[x].push_back(make_pair(c, y));
    }

    t[1]=1;
    h.push({0, 1});
    for(i=2;i<=n;i++) {
        t[i]=maxm;
    }
    while(!h.empty()) {
            nod=h.top().second;
            h.pop();
            ct[nod]=0;
            for(i=0;i<v[nod].size();i++) {
                    newn=v[nod][i].second;
                    cost=v[nod][i].first;
                    if(t[newn]>t[nod]+cost) {
                            t[newn]=t[nod]+cost;
                            if(ct[newn]==0) {
                                    ct[newn]=1;
                                    h.push({-t[newn], newn});
                            }
                    }
            }
    }
    for(i=2;i<=n;i++) {
          if(t[i]==maxm) {
            fout<<"0 ";
          }
          else {
                fout<<t[i]-1<<" ";
          }
    }

    return 0;
}