#include <fstream>
#include <vector>
#define INF 1008099002
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[50011];
vector<pair<int,int> > L[50011];
vector<pair<int,int> >::iterator it;

int main(void){
    register int i,j,x,c,y;
    pair<int,int> p;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
    for(i=2;i<=n;i++) D[i]=INF;

    bool ok;
    do{ok=false;
        for(i=1;i<=n;i++){
            if(D[i]==INF) continue;
            for(it=L[i].begin();it!=L[i].end();it++){
                p=*it;
                if(D[i]+p.second<D[p.first])
                    D[p.first]=D[i]+p.second,ok=true;
            }
        }
    }while(ok);

    for(i=2;i<=n;i++)
        g<<D[i]<<" ";
    f.close();
    g.close();
    return 0;
}