#include <fstream>
#include <vector>
#include <queue>

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 < int > G[Nmax];
vector < int > C[Nmax];


void Read() {

    fin >> N >> M;
    while(M--){

        int X; int Y; int D;
        fin >> X >> Y >> D;

        G[X].push_back(Y);
        C[X].push_back(D);
    }
}

void Dijkstra(int Start){

    priority_queue < pair <int, int>, vector<pair<int, int> >, greater<pair <int, int> > > Q;

    int Distance[Nmax];

    for(int i = 0 ;i <= N; ++i) Distance[i] = Inf;

    Distance[Start] = 0;

    Q.push(make_pair(0, Start));

    while(!Q.empty()) {

         int Nod = Q.top().second; int val = Q.top().first;
         Q.pop();

        for(int i = 0; i < G[Nod].size(); ++i){
            if(Distance[G[Nod][i]] > val + C[Nod][i]){

                Distance[G[Nod][i]] = val + C[Nod][i];

                Q.push(make_pair(Distance[G[Nod][i]], G[Nod][i]));

            }
        }
    }

    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;
}