#include <fstream>
#include <queue>
#include <vector>

using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
struct el
{
    int nod,cost;
    bool operator < (const el &A) const{
        return cost > A.cost;
    }
};
priority_queue < el > q;
vector < el > v[25005];
int n,m,x,y,z;
int distante[25005];
void Dijkstra()
{
    q.push({1,0});
    while (!q.empty())
    {
        int valoare=q.top().cost;
        int nod =q.top().nod;
        for (int i=0;i<v[nod].size();i++)
        {
            el vecin=v[nod][i];
            if ((distante[nod]+vecin.cost < distante[vecin.nod]) || (distante[vecin.nod]==0))
            {
                distante[vecin.nod]=distante[nod]+vecin.cost;
                q.push({vecin.nod,distante[vecin.nod]});
            }
        }
        q.pop();
    }
}
int main()
{
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        cin >> x >> y >> z;
        v[x].push_back({y,z});
    }
    Dijkstra();
    for (int i=2;i<=n;i++)
        cout << distante[i] << " ";
    return 0;
}