#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

const int oo=(1<<30);
vector < pair<int,int> > graf[50001];
int distMin[50001];
bool incoada[50001];

struct HeapComparator
{
    bool operator() (int posA,int posB)
    {
        return distMin[posA]>distMin[posB];
    }
};

priority_queue <int, vector<int>, HeapComparator> heap;

int N,M;

void solve()
{
    for (int i=1;i<=N;i++)
        distMin[i] = oo;
    distMin[1] = 0;
    heap.push(1);
    incoada[1] = 1;
    while (!heap.empty())
    {
        int nod_curent = heap.top();
        heap.pop();
        incoada[nod_curent] = 0;
        for (size_t i=0;i<graf[nod_curent].size();i++)
        {
            int nou = graf[nod_curent][i].first;
            int cost = graf[nod_curent][i].second;
            if (distMin[nou]>distMin[nod_curent]+cost)
            {
                distMin[nou] = distMin[nod_curent]+cost;
                if(!incoada[nou])
                {
                    heap.push(nou);
                    incoada[nou] = 1;
                }
            }
        }
    }
}

void read()
{
    int a,b,c;
    fin>>N>>M;
    for (int i=1;i<=M;i++)
    {
        fin>>a>>b>>c;
        graf[a].push_back(make_pair(b,c));
    }
}

int main()
{
    read();
    solve();
    for (int i=2;i<=N;i++)
    {
        if (distMin[i]==oo) fout<<"0 ";
        else fout<<distMin[i]<<' ';
    }
    return 0;
}