#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <climits>

using namespace std;

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


const int NMax = 50003;
int N, M, dist[NMax];

vector <pair<int, int> > G[NMax];
multiset <pair<int, int> > heap;

void Read()
{
    in >> N >> M;
    for(int i = 1;i<=M;++i)
    {
        int x,y,c;
        in >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
    for(int i = 2;i<=N;++i)
        dist[i] = INT_MAX;
    heap.insert(make_pair(0,1));
}

void Dijkstra()
{
    while(!heap.empty())
    {
        int Nod = heap.begin()->second;
        //int d = heap.begin()->first;
        heap.erase(heap.begin());

        for(int i = 0; i<(int) G[Nod].size(); ++i)
        {
            int Vecin = G[Nod][i].first;
            int cost = G[Nod][i].second;
            if(dist[Vecin] > dist[Nod] + cost)
            {
                if(dist[Vecin] != INT_MAX)
                    heap.erase(heap.find(make_pair(dist[Vecin],Vecin)));
                dist[Vecin] = dist[Nod] + cost;
                heap.insert(make_pair(dist[Vecin], Vecin));
            }
        }
    }
}

void Print()
{
    for(int i = 2;i<=N;++i)
    {
        if(dist[i] == INT_MAX)
            dist[i] = 0;
        out << dist[i] << ' ';
    }
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}