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

using namespace std;

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

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

int N,M,dist[NMax];

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(1,0));
}

void Dijkstra()
{
    while(!heap.empty())
    {
        int Nod = 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(Vecin, dist[Vecin])));
                }
                dist[Vecin] = dist[Nod] + cost;
                heap.insert(make_pair(Vecin, dist[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;
}