#include <bits/stdc++.h>

using namespace std;
#define INF  INT_MAX
vector < pair <int, int> > G[50001];
priority_queue <pair <int, int>, vector <pair <int, int> > ,greater <pair <int,int> > > Q;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,dist[50001];
bool viz[50001];
void read()
{
    int i,a,b,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>a>>b>>c;
        G[a].push_back({c,b});
    }
}
void init()
{
    int i;
    Q.push({0,1});
    for(i=2;i<=n;i++)
        dist[i]=INF,viz[i]=0;

}
void Dijkstra()
{
    int node,cost;
    while(!Q.empty())
    {
        node=Q.top().second;

        if(viz[node]!=1)
        {
            viz[node]=1;
            cost=Q.top().first;

            for( auto x: G[node])
            if(x.first+cost<dist[x.second]) { Q.push(make_pair(x.first+dist[node],x.second));
            dist[x.second]=x.first+cost;
            }
        }

Q.pop();
    }
}

int main()
{
    read();
    init();
    Dijkstra();
    for(int i=2; i<=n;i++)
        g<<dist[i]<<" ";

}