#include <fstream>
#include <queue>
#include <vector>

const int MAXN = 50000 + 1;
const int INF = 0x7fffffff;

using namespace std;

int N, M;
int dist[MAXN];
vector< int> graf[MAXN], costs[MAXN];
queue <int> Q;

void read()
{
    ifstream fin("dijkstra.in");

    fin >> N >> M;

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

    fin.close();

}

void solve()
{
    int i, nod, nod2, costcrt, l;

    for(i = 2; i <= N; ++i) dist[i] = INF;
    //adaugam primul nod in coada
    Q.push(1);

    //cat timp mai avem elemente in coada
    while(Q.size() > 0)
    {
        //luam primul element din COADA si il eliminam
        nod = Q.front();
        Q.pop();
        //in variabila costcrt retinem distanta minima a nodului NOD
        costcrt = dist[nod];
        //in variabila l retinem cati vecini are nodul NOD
        l = graf[nod].size();
        //parcurgem toti vecinii nodului NOD
        for(i = 0; i < l; ++i)
        {
            //luam vecinul curent
            nod2 = graf[nod][i];
            //daca distanta vecinului curent este mai mare decat distanta nodului NOD  + costul dintre NOD si vecinul curent
            if(dist[nod2] > costcrt + costs[nod][i])
            {
                dist[nod2] = costcrt + costs[nod][i];
                Q.push(nod2);
            }

        }

    }
}

void write()
{
    ofstream fout("dijkstra.out");

    for (int i = 2; i <= N; i++)
    {
        if (dist[i] == INF) dist[i] = 0;
        fout << dist[i] << ' ';
    }

    fout.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}