#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[50005],n,m,x,y,c,i;
vector< pair<int, int> > v[50005];
priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
void dijkstra(int nod)
{
    memset(d,inf,sizeof(d));
    Q.push({0,nod});
    d[nod]=0;
    while(!Q.empty())
    {
        int cost=Q.top().second;
        int j=Q.top().first;
        Q.pop();
        for(i=0;i<v[cost].size();i++)
            if(d[v[cost][i].first]>d[cost]+v[cost][i].second)
            {
                d[v[cost][i].first]=d[cost]+v[cost][i].second;
                Q.push({d[v[cost][i].first],v[cost][i].first});
            }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            d[i]=0;
        fout<<d[i]<<" ";
    }
    fout<<"\n";
    fin.close();
    fout.close();
    return 0;
}