#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define INF 20000001
#define noduri 50002
using namespace std;
int n,m,R=1;

struct graf
{
    int nod, cost;
    graf *next;
};

graf *a[noduri];

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
void Read()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int x,y,cost;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        add(x,y,cost);
    }
}

void Dijkstra()
{
    set < pair<int, int> > setds;
    vector<int> dist(n+1, INF);
    ofstream g("dijkstra.out");
    setds.insert(make_pair(0, R));
    dist[R] = 0;
    while (!setds.empty())
    {
        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());

        int u = tmp.second;

        for (graf *q=a[u]; q; q=q->next)
        {
            int v = q->nod;
            int weight = q->cost;

            if (dist[v] > dist[u] + weight)
            {
                if (dist[v] != INF)
                    setds.erase(setds.find(make_pair(dist[v], v)));
                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }

        for(int i=2;i<=n;i++)
            {
                if(dist[i]==INF)
                    g<<0<<" ";
                else g<<dist[i]<<" ";
            }
}

int main()
{
    Read();
    Dijkstra();
    return 0;
}