# include <fstream>
# include <vector>
# define INF 1000000000
# define DIM 50010
# define f first
# define s second
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int> > Lista[DIM];
pair <int,int> d[DIM],h[DIM];
int drum[DIM],n,m,i,j,x,y,cost,t,nc,nv;
void add(int poz){
    t++;
    d[poz].s=t;
    h[t].f=d[poz].f;
    h[t].s=poz;
    int c=t,p=t/2;
    while(p!=0){
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void change(int poz){
    int poz1=h[poz].s;
    h[poz].f=d[poz1].f;
    int c=poz,p=poz/2;
    while(p!=0){
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void off(){
    d[h[1].s].f=-INF;
    h[1]=h[t--];
    d[h[1].s].s=1;
    int p=1,c=2;
    while(c<=t){
        if(h[c+1].f<h[c].f&&c+1<=t)
            c++;
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            p=c;
            c*=2;
        }
        else
            break;
    }
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        Lista[x].push_back(make_pair(y,cost));
    }
    add(1);
    for(i=2;i<=n;i++){
        d[i].f=INF;
        add(i);
    }
    for(i=1;i<=n;i++){
        nc=h[1].s;
        off();
        for(j=0;j<Lista[nc].size();j++){
            nv=Lista[nc][j].f;
            cost=Lista[nc][j].s;
            if(cost<=d[nv].f){
                d[nv].f=cost;
                drum[nv]=drum[nc]+cost;
                change(d[nv].s);
            }
        }
    }
    for(i=2;i<=n;i++)
        fout<<drum[i]<<" ";
    fout<<"\n";
    return 0;
}