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

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n, m;
int drum[50005];
vector < pair < int, int > > a[50005];
queue < int > coada;

void Dijkstra (int start)
{
   coada.push(start);
   while (!coada.empty())
   {
       int nod = coada.front();
       int lg = a[nod].size() - 1;
       coada.pop();
        for (int i=0; i<=lg; i++)
        {
            if (drum[a[nod][i].first] == 0)
            {
                drum[a[nod][i].first] = drum[nod] + a[nod][i].second;
                coada.push(a[nod][i].first);
            }
            else if (drum[nod] + a[nod][i].second < drum[a[nod][i].first])
            {
                drum[a[nod][i].first] = drum[nod] + a[nod][i].second;
                coada.push(a[nod][i].first);
            }
        }
   }
}

int main()
{
   f >> n >> m;
   for (int i=1; i<=m; i++)
   {
       int x, y, val;
       f >> x >> y >> val;
       a[x].push_back(make_pair(y, val));
   }

   Dijkstra(1);

   for (int i=2; i<=n; i++)
     g << drum[i] << " ";
    return 0;
}