#include<bits/stdc++.h>
#define NMAX 50005
#define s second
#define f first
 
using namespace std;
 
const int inf=(1<<30);
 
int n,m,x,y,c;
int d[NMAX];
bool inQ[NMAX];
 
 
 
struct comp {
    bool operator() (int x, int y) {
        return d[x]>d[y];
    }
};
 
priority_queue <int, vector<int>, comp> Q;
vector <pair<int,int> >V[NMAX];
 
void Dijkstra(int start){
     
    for (int i=1; i<=n; i++) {
        d[i]=inf;
    }
     
    d[start]=0;
     
    Q.push(start);
    inQ[start]=1;
    while (!Q.empty()) {
         
        int cost,y;
        x = Q.top(); Q.pop();
        inQ[x] = 0;
         
        for (int i=0; i<V[x].size(); i++) {
            cost = V[x][i].s;
            y = V[x][i].f;
            if (cost+d[x]<d[y]) {
                d[y] = cost+d[x];
                 
                if (!inQ[y]) Q.push(y), inQ[y]=1;
            }
        }
         
    }
}
 
int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
     
    for (int i=0; i<m; i++) {
        cin>>x>>y>>c;
         
        V[x].push_back(make_pair(y,c));
    }
     
    Dijkstra(1);
     
    for (int i=2; i<=n; i++) {
        if (d[i]==inf) cout<<"0 ";
        else cout<<d[i]<<' ';
    }
     
     
     
    return 0;
}