#include <fstream>
#include <vector>
#include <set>
#define VAL 50005
#define INF 1000000000

using namespace std;

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

int N, M, i, j, A, B, C;
int dist[VAL], cost, nod;
vector < pair <int, int> > G[VAL];
vector < pair <int, int> > :: iterator it;
multiset < pair <int, int> > Heap;
multiset < pair <int, int> > :: iterator it2;

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B >> C;
        G[A].push_back(make_pair(B, C));
    }
    for (i=2; i<=N; i++)
    {
        dist[i]=INF;
        Heap.insert(make_pair(dist[i], i));
    }
    Heap.insert(make_pair(0, 1));
    for (i=1; i<=N; i++)
    {
        it2=Heap.begin();
        nod=it2->second;
        Heap.erase(Heap.begin());
        for (it=G[nod].begin(); it!=G[nod].end(); it++)
        {
            if (dist[it->first]>dist[nod]+it->second)
            {
                it2=Heap.find(make_pair(dist[it->first], it->first));
                Heap.erase(it2);
                dist[it->first]=dist[nod]+it->second;
                Heap.insert(make_pair(dist[it->first], it->first));
            }
        }
    }
    for (i=2; i<=N; i++)
    {
        if (dist[i]==INF)
          dist[i]=0;
        fout << dist[i] << " ";
    }
    fin.close();
    fout.close();
    return 0;
}