#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int VAL=50005;
const int INF=2000000000;

int N, M, i, j, cost[VAL], A, B, C, nod;
set < pair <int, int> > Heap;
set < pair <int, int> > :: iterator itH;
vector < pair <int, int> > G[VAL];
vector < pair <int, int> > :: iterator itG;

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