#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
struct muchie {
    int nod,dist;
};
 
struct comp {
    bool operator()(muchie &a,muchie &b) {
        return a.dist>b.dist;
    }
};
 
priority_queue <muchie,vector<muchie>,comp> q;
vector <muchie> v[50005];
unsigned int dist[50005];
int n,m;
 
 
muchie mk_muchie(int nod,int dist) {
    muchie nou;
    nou.nod = nod;
    nou.dist = dist;
    return nou;
}
 
int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=2;i<=n;i++) dist[i] = 0xffffffff;
 
        for (int j=1;j<=m;j++) {
                int t,f,c;
                scanf("%d %d %d",&t,&f,&c);
                v[t].push_back(mk_muchie(f,c));
        }
 
    q.push(mk_muchie(1,0));
    while (!q.empty()) {
        muchie n = q.top(); q.pop();
 	int nrad = v[n.nod].size();
        for(unsigned int i=0;i < nrad;++i){
                muchie nou = v[n.nod][i];
                unsigned int nod = nou.nod, dst = nou.dist;
                if (dist[nod] > n.dist + dst ) {
                    dist[nod] = n.dist + dst;
                    q.push(mk_muchie(nod,dist[nod]));
                }
        }
    }
    for (int i=2;i<=n;i++) {
        if (dist[i] != 0xffffffff) printf("%d ",dist[i]);
        else printf("0 ");
    }
    return 0;
}