#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 50010
using namespace std;
const int  inf =1000000;
vector <pair<int,int> > graf[Nmax];
priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > coada;
int n,m;
int cost[Nmax];


void read()
{
    int x,y,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 0 ; i < m ;  i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        graf[x].push_back({y,c});
    }
    for(int i= 2 ; i <= n;  i++)
        cost[i] = inf;
}

void dijkstra()
{
    coada.push({0,1});
    while(!coada.empty())
    {
        int nod = coada.top().second;
        int costul = coada.top().first;
        coada.pop();
        if(cost[nod] != costul)
            continue;
        int limita = graf[nod].size();
        for(int i = 0 ; i < limita ; i++)
        {
            int vecin = graf[nod][i].first;
            int costmuchie =graf[nod][i].second;
            if(cost[nod] + costmuchie < cost[vecin])
            {
                cost[vecin] = cost[nod] + costmuchie;
                coada.push({costmuchie,vecin});
            }
        }
    }
}

void afisare()
{
    for(int i = 2 ; i <= n ; i++)
    {
        if(cost[i] == inf)
            printf("%d ",0);
        else
            printf("%d ",cost[i]);
    }
}


int main()
{
    read();
    dijkstra();
    afisare();
    return 0;
}