#include <fstream>
#include <vector>
#include <set>

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

const int Nmax = 50006;
const int Inf = (1<<30);

int N; int M;

vector < pair <int, int> > G[Nmax];


void Read() {

    fin >> N >> M;
    while(M--){
        int X; int Y; int D;
        fin >> X >> Y >> D;
        G[X].push_back(make_pair(Y,D));
    }
}

void Dijkstra(int Start){

    set < pair<int, int> > S;
    int Distance[Nmax];
    for(int i = 0 ;i <= N; ++i) Distance[i] = Inf;

    Distance[Start] = 0;

    S.insert(make_pair(0, Start));

    while(!S.empty()) {

         int Nod = (*S.begin()).second;
         int val = (*S.begin()).first;

        S.erase(*S.begin());


        for(vector<pair<int, int> >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it){
            if(Distance[it -> first] > val + it -> second){

              //S.erase(S.find(make_pair(Distance[it -> second], it -> first)));
                Distance[it -> first] = val + it -> second;

                S.insert(make_pair(Distance[it -> first], it -> first));

            }
        }
    }

    for(int i = 2; i <= N; ++i){
        if(Distance[i] == (1<<30))
            fout << 0 <<" ";
        else fout << Distance[i] <<" ";
    }
}


int main() {

    Read();

    Dijkstra(1);
    return 0;
}