#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define ios ios_base::sync_with_stdio(false);
#define NMAX 50005
#define INF INT_MAX

using namespace std;

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

int n,m,i;
int d[NMAX];
bool e[NMAX];

vector < pair <int,int> > g[NMAX];

struct compara
{   bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};


priority_queue<int, vector<int>, compara> c;

void citire(){
    cin>>n>>m;
    for (i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(make_pair(y,z));
    }
}

void Dijkstra(int ns){
    for (i=1;i<=n;i++) d[i]=INF;
    d[ns]=0;
    c.push(ns);
    e[ns]=true;

    while (!c.empty()){
        int nc=c.top();
        c.pop();
        e[nc]=false;
    for (i=0;i<g[nc].size();i++){
        int vec=g[nc][i].first;
        int cost=g[nc][i].second;
        if (d[nc]+cost<d[vec]){
            d[vec]=d[nc]+cost;
            if(e[vec]==false) {c.push(vec); e[vec]=true;}
        }
    }
    }
}

void afis(){
    for(i=2;i<=n;i++)
        if (d[i]!=INF) cout<<d[i]<<" ";
        else cout<<0<<" ";
}

int main()
{
    ios;
    cin.tie(0);
    cout.tie(0);
    citire();
    Dijkstra(1);
    afis();
    return 0;
}