#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int dmin[50001],prec[50001];
vector<pair<int,int> > G[50001];
class comparVf{
    public:
    bool operator()(int&x,int&y){
        return dmin[x]>dmin[y];
    }
};
priority_queue<int, vector<int>,comparVf> coada;
void drum(int x){
    if(x!=0){
        drum(prec[x]);
        printf("%d ",x);
    }
}
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,m,n,n1,n2,x0,c,nod;
    scanf("%d%d",&n,&m);
    x0=1;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&n1,&n2,&c);
        G[n1].push_back(make_pair(n2,c));
    }
    for(i=1;i<=n;i++){
        dmin[i]=1000000000;
        prec[i]=x0;
    }
    dmin[x0]=0;
    prec[x0]=0;
    coada.push(x0);
    while(!coada.empty()){
        nod=coada.top();
        coada.pop();
        for(i=0;i<G[nod].size();i++)
            if(dmin[G[nod][i].first]> dmin[nod]+G[nod][i].second){
                dmin[G[nod][i].first]=dmin[nod]+G[nod][i].second;
                prec[G[nod][i].first]=nod;
                coada.push(G[nod][i].first);
            }
    }
    for(i=1;i<=n;i++)
        if(i!=x0)
            if(dmin[i]==1000000000)
                printf("0 ");
            else
                printf("%d ",dmin[i]);
    return 0;
}