#include <cstdio>
#include <queue>
using namespace std;

const int N_MAX = 50010;

const int INF = 1000000000;

struct vcn
{
    int dest; int cost;
};

vector<vcn> vecin[N_MAX]; int n;
int d[N_MAX]; //cost total, ii marchez direct valoarea finala (valorile intermediare zboara prin heap)
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > heap;

void citeste()
{
    int m,a,b,c;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        vecin[a].push_back((vcn){b,c});
    }
}

void initializare_dijkstra(int s)
{
    for (int i = 1; i <= n; ++i)
            d[i] = INF;
    heap.push(make_pair(0,s));
}

void dijkstra(int s)
{
    //golire heap
    initializare_dijkstra(s);
    int nod,c;
    while (!heap.empty())
    {
        nod = heap.top().second;
        c = heap.top().first;
        heap.pop();
        if (d[nod] != INF) //are deja calculata distanta finala, deci am marcat deja in jur cu el
            continue;
        d[nod] = c; //aceasta distanta tentativa dintre toate e minima, deci devine finala si marcheaza in jur
        for (unsigned int i = 0; i < vecin[nod].size(); ++i)
            heap.push(make_pair(c + vecin[nod][i].cost,vecin[nod][i].dest)); //marchez asa in heap distantele tentative
    }
}

void scrie()
{
    for (int i = 2; i <= n; ++i)
        printf("%d ",(d[i] != INF)?d[i]:0);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citeste();
    dijkstra(1);
    scrie();
    return 0;
}