#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];
bool vizitat[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});
    }
}

void dijkstra()
{
    coada.push({0,1});

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

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


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