#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 50005
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int d[nmax];
struct cmp
{
    bool operator()(int a,int b)
    {
        return d[a]>d[b];
    }
};
struct nod
{
    int u,cost;
};vector <nod> v[250005];
priority_queue  <int,vector<int>,cmp> q;
int main()
{   int n,m;
    iostream::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {   int a,b,c;
    cin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    q.push(1);
    while(!q.empty())
    {
        int node=q.top();
        q.pop();
            for(int i=0;i!=v[node].size();++i)
            {
                nod u=v[node][i];
                if(d[u.u]==0||d[u.u]>d[node]+u.cost)
                {
                    d[u.u]=d[node]+u.cost;
                    q.push(u.u);
                }
            }
    }
    for(int i=2;i<=n;++i)
        cout<<d[i]<<" ";
    return 0;
}