#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define x first
#define y second
int n, res[50009];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> h;
vector<pair<int, int>> G[50009];
void rd()
{
  int a, b, c;
  f>>n>>a;
  while(f>>a>>b>>c)
    G[a].push_back(make_pair(b, c));
  for(int i=1; i<=n; i++)
        res[i]=1<<30;
}
void Dijkstra()
{
    h.push(make_pair(0, 1));
    while(h.size())
    {
        pair<int, int> X=h.top();
        h.pop();
        if(res[X.y]!=(1<<30))
            continue;
        res [X.y]=X.x;
        for (auto a:G[X.y])
            h.push(make_pair(res[X.y]+a.y, a.x));
    }
}
void afis()
{
  for (int i=2; i<=n; i++)
        if (res[i]==(1<<30))g<<"0 ";
        else g<<res[i]<<' ';
    g<<'\n';
}
int main()
{
    rd();
    Dijkstra();
    afis();
    f.close();
    g.close();
    return 0;
}