#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector <pair<int,int>> g[50001];
set <pair<int,int>> p;
int d[50001];
#define inf 1e9;
int main()
{
    int n,m,a,b,c,i;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    for(auto x : g[1])
    {
        d[x.first]=x.second;
        p.insert(make_pair(x.second,x.first));
    }
    while(!p.empty())
    {
        a=p.begin()->second;
        p.erase(p.begin());
        for(auto x : g[a])
        {
            if(d[a]+x.second<d[x.first])
            {
                p.erase(make_pair(d[x.first],x.first));
                d[x.first]=d[a]+x.second;
                p.insert(make_pair(d[x.first],x.first));
            }
        }
    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<" ";
    return 0;
}