#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("dijkstra.in");
ofstream g("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 w=q.top().second;
        int d1=q.top().first;
        q.pop();
        if(d1==d[w])
            for(i=0;i<v[w].size();i++)
                if(d[v[w][i].first]>d[w]+v[w][i].second)
                {
                    d[v[w][i].first]=d[w]+v[w][i].second;
                    q.push({d[v[w][i].first],v[w][i].first});
                }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y,c});
    }
    ///cout<<inf;
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            d[i]=0;
        g<<d[i]<<" ";
    }
    g<<"\n";
    f.close();
    g.close();
    return 0;
}