#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
const int NMax = 50002;
const int oo = (1 << 30);
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
unsigned int N, M;
vector <pair<int, int> > G[NMax];
bool inCoada[NMax];
int D[NMax];
struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue<int, vector<int>, compara> q;

void citire()
{
    f>>N>>M;
    for (unsigned int i=1; i<=M; i++)
    {
        int sursa, destinatie, cost;
        f>>sursa>>destinatie>>cost;
        G[sursa].push_back(make_pair(destinatie, cost));
    }
}
void afisare()
{
    for (unsigned int i=2; i<=N; i++)
        if (D[i]!=oo)
            g<<D[i]<<" "; else
            g<<"0"<<" ";
}

void dijkstra(int nod)
{
    for (unsigned int i=1; i<=N; i++)
        D[i]=oo;
    D[nod]=0;
    inCoada[nod]=true;
    q.push(nod);
    int nodCurent;
    while (!q.empty())
    {
        nodCurent=q.top();
        q.pop();
        inCoada[nodCurent]=false;
        for (unsigned int i=0; i<G[nodCurent].size(); i++)
        {
            int next=G[nodCurent][i].first;
            int cost=G[nodCurent][i].second;
            if (D[next]>D[nodCurent]+cost)
            {
                D[next]=D[nodCurent]+cost;
                if (inCoada[next]==false)
                {
                    inCoada[next]=true;
                    q.push(next);
                }
            }
        }
    }
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}