#include <bits/stdc++.h>
#define PII pair<int,int>
#define Nod second
#define Cost first
#define Inf 1000000000

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <PII> gf[50001];
int n,m;
priority_queue<PII,vector<PII>,greater<PII>> c;
int drum[50001];
bitset <50001> viz;

int main()
{
    in>>n>>m;

    for(int i,j,cost,k=1;k<=m;k++)
    {
        in>>i>>j>>cost;

        gf[i].push_back({cost,j});
    }

    int start=1;

    int nrViz=0;

    for(int i=1;i<=n;i++)
        drum[i]=Inf;

    drum[start]=0;
    c.push({0,start});

    while(nrViz<n)
    {
        while( viz[ c.top().Nod ] )
            c.pop();

        int nod=c.top().Nod;
        int dist=c.top().Cost;
        c.pop();

        viz[nod]=1;nrViz++;

        for(auto vec:gf[nod])
            if( drum[vec.Nod] > vec.Cost+dist )
            {
                drum[vec.Nod]=vec.Cost+dist;
                c.push({ drum[vec.Nod] , vec.Nod });
            }
    }

    for(int i=2;i<=n;i++)
        if(drum[i]!=Inf)
            out<<drum[i]<<' ';
        else
            out<<0<<'\n';

    return 0;
}