#include<fstream>
#include<queue>
#include<vector>
#include<limits.h>
using namespace std;

int N;      //csucsok szama

struct el {
    unsigned short cel;
    short hossz;
};

struct csucsok {
    unsigned short pont;
    bool latogatott=false;
    vector<el> szomszedok;
    long long tavolsag = LLONG_MAX;                        //megj.
};

struct compare
{
    bool operator()(csucsok& l, csucsok& r)
    {
        return l.tavolsag > r.tavolsag;
    }
};
priority_queue<csucsok, vector<csucsok>, compare > sor;         //&

vector<csucsok> csucs;

void read() {
    int M;      //utak szama
    ifstream in("dijkstra.in");
    in >> N >> M;
    for (int i = 0;i < N;++i) {
        csucsok temp;
        temp.pont = i;
        csucs.push_back(temp);
    }
    for (int i = 0;i < M;++i) {
        unsigned short A, B, C;
        in >> A >> B >> C;
        A--; B--;
        el temp;
        temp.cel = B;
        temp.hossz = C;
        csucs[A].szomszedok.push_back(temp);
    }
    in.close();
}

void dijkstra(short int kezdopont) {
    csucs[kezdopont].latogatott = true;
    sor.pop();
    vector<el>::iterator iterator;
    for (iterator = csucs[kezdopont].szomszedok.begin(); iterator != csucs[kezdopont].szomszedok.end();iterator++) {
        if (!csucs[(*iterator).cel].latogatott) {
            if (csucs[kezdopont].tavolsag + (*iterator).hossz < csucs[(*iterator).cel].tavolsag) {
                csucs[(*iterator).cel].tavolsag = csucs[kezdopont].tavolsag + (*iterator).hossz;
                csucsok start;
                start.pont = (*iterator).cel;
                start.tavolsag = csucs[(*iterator).cel].tavolsag;
                sor.push(start);
            }
        }
    }
    while (!sor.empty())
        if (!sor.top().latogatott) {
            dijkstra(sor.top().pont);
            break;
        }
        else sor.pop();
}

void print() {
    ofstream out("dijkstra.out");
    for (int i = 1;i < N;++i) {
        if(i!=N-1)
        if (csucs[i].tavolsag == LLONG_MAX) out << 0 << " ";
        else out << csucs[i].tavolsag << " ";
        else
            if (csucs[i].tavolsag == LLONG_MAX) out << 0;
            else out << csucs[i].tavolsag;
    }
    out.close();
}

int main() {
    read();

    sor.push(csucs[0]);
    csucs[0].tavolsag = 0;
    dijkstra(0);
    print();
}