#include <fstream>
#include <vector>

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct muchie{
    int dist , nod;
    muchie(int d1 , int n1){
        dist=d1;
        nod=n1;
    }
};

struct noduri {
    vector<muchie> next;
    int dist;
    int nod;
    noduri(int i){
        dist=-1;
        nod = i;
    }
};

int main() {
    int n , m;
    vector<noduri> nod;
    vector<int> coada;
    fi>>n>>m;
    for(int i=0;i<n;i++)
    nod.push_back(noduri(i));
    for(int i=0;i<m;i++){
        int x, y ,d;
        fi>>x>>y>>d;
        nod[x-1].next.push_back(muchie(d,y-1));
    }
    coada.push_back(0);
    for(int i=0;i<(signed)coada.size();i++){
        for(int j=0;j<(signed)nod[coada[i]].next.size();j++){
            int * distAct=&nod[coada[i]].dist;
            int * distAdd=&nod[coada[i]].next[j].dist;
            int * distNext=&nod[nod[coada[i]].next[j].nod].dist;
            if((*distAct)==-1)(*distAct)=0;
            if((*distNext)==-1)(*distNext)=2000000000;
            if((*distAct)+(*distAdd)<(*distNext)){
                (*distNext)=(*distAct)+(*distAdd);
                coada.push_back(nod[nod[coada[i]].next[j].nod].nod);
            }
        }
    }
    for(int i=1;i<n;i++){
        fo<<nod[i].dist<<' ';
    }
}