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

using namespace std;

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

const int Nmax = 50007;
const int Mmax = 250009;
const int Inf = (1<<30);

int N; int M;

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

void Read() {

    fin >> N >> M;

    while(M--) {
        int A, B, C;

        fin >>A >> B >> C;
        G[A].push_back(make_pair(B, C));
    }

}


void Initialize(bool Visited[], int MinDistance[], int S ) {

    for(int i = 0 ;i < Nmax ; ++i) Visited[i] = false, MinDistance[i] = Inf;

    MinDistance[S] = 0; Visited[S] = true;
}

int* Dijkstra(int Sursa) {

    bool Visited[Nmax]; int MinDistance[Nmax];

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

    Initialize(Visited, MinDistance, Sursa);
    Q.push( make_pair(0 , 1));

    while( !Q.empty()) {

        int Node = Q.top().second;
        int C = Q.top().first;

        Q.pop();

        for(int i = 0 ; i < G[Node].size(); ++i) {

            if(MinDistance[G[Node][i].first] > C + G[Node][i].second) {

                MinDistance[G[Node][i].first] = C + G[Node][i].second;

                Q.push(make_pair(MinDistance[G[Node][i].first], G[Node][i].first) );
            }
        }
    }

    return MinDistance;
}


void Solve() {

    Dijkstra(1);
}


void Write(int Distance[]) {

    for(int i = 2; i <= N; ++i)
        if(Distance[i] == Inf)
            fout << 0 << " ";
        else fout << Distance[i] << " ";

}

int main() {

    Read(); Write(Dijkstra(1));

    fin.close();

    return 0;
}