#include <fstream>
#include <vector>

using namespace std;

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

const int oo = 1000000005;

int N, M;
int dist[50005], inHeap[50005], heapSize;
pair <int, int> heap[50005];
vector < pair <int, int> > g[50005];
bool vis[50005];

void Insert(pair <int, int> node)
{
    heapSize++;
    heap[heapSize].first = node.first;
    heap[heapSize].second = node.second;
}

void DownHeap(int index)
{
    int Son = index * 2;

    if(Son + 1 <= heapSize && heap[Son].second > heap[Son + 1].second)
        Son++;

    if(Son <= heapSize && heap[Son].second < heap[index].second)
    {
        swap(inHeap[heap[Son].first], inHeap[heap[index].first]);
        swap(heap[Son], heap[index]);
        DownHeap(Son);
    }
}

void UpHeap(int index)
{
    int Father = index / 2;

    if(Father && heap[Father].second > heap[index].second)
    {
        swap(inHeap[heap[Father].first], inHeap[heap[index].first]);
        swap(heap[Father], heap[index]);

        UpHeap(Father);
    }
}

pair <int, int> ExtractMin()
{
    int minNode = heap[1].first, minDist = heap[1].second;

    swap(inHeap[heap[1].first], inHeap[heap[heapSize].first]);
    swap(heap[1], heap[heapSize]);
    heapSize--;
    DownHeap(1);

    return make_pair(minNode, minDist);
}

void Update(int index, int value)
{
    heap[index].second = value;
    UpHeap(index);
}

int main()
{
    fin >> N >> M;

    int x, y, c;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }

    Insert({1, 0});
    dist[1] = 0, inHeap[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        dist[i] = oo, inHeap[i] = i;
        Insert({i, oo});
    }

    int eraseCount = 0;
    while(eraseCount < N)
    {
        eraseCount++;

        pair <int, int> p = ExtractMin();
        int currentNode = p.first;
        int currentDist = p.second;

        dist[currentNode] = currentDist;
        vis[currentNode] = true;

        for(auto muchie : g[currentNode])
        {
            int vecin = muchie.first;
            int cost = muchie.second;
            int currentDistToVecin = heap[inHeap[vecin]].second;

            if(!vis[vecin])
            {
                int newCost = dist[currentNode] + cost;

                if(newCost < currentDistToVecin)
                    currentDistToVecin = newCost;
            }

            if(currentDistToVecin < heap[inHeap[vecin]].second)
                Update(inHeap[vecin], currentDistToVecin);
        }
    }

    for(int i = 2; i <= N; i++)
        fout << ((dist[i] == oo) ? 0 : dist[i]) << ' ';

    return 0;
}