#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector <pair <int, int> >  g[50001];
priority_queue <pair <int, int> > q;
long long d[50001],n,m,x,y,c,viz[50001];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++)
        d[i]=100000000;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        while(!q.empty() && viz[x] == 1)
        {
            x = q.top().second;
            q.pop();
        }
        viz[x] = 1;
        for( int i = 0; i < g[x].size(); i++)
            if(g[x][i].second + d[x] < d[g[x][i].first])
            {
                d[g[x][i].first] = g[x][i].second + d[x];
                q.push(make_pair(-d[g[x][i].first], g[x][i].first));
            }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==100000000) d[i]=0;
        cout<<d[i]<<' ';
    }
    return 0;
}