#include <fstream>
#include <vector>
#include <set>
#define infinit 0x3f3f3f3f

using namespace std;


void citire(int &n, vector< pair <int, int> >* &la)
{
    ifstream f("dijkstra.in");
    int m, x, y;
    int c;

    f >> n >> m;

    //memo G prin lista de muchii
    la = new vector< pair <int, int> >[n+1];

    for(int i=1; i<=m; i++)
    {
        f >> x >> y >> c;
        la[x].push_back( {y, c} );
    }
    f.close();
}

void Dijkstra(int n, vector< pair <int, int> >*la, int sursa)
{

    int *d = new int [n+1];

    int u, v;
    int w_uv;

    for(int i=0; i<n; i++)
    {
      d[i] = infinit;
    }

    d[sursa] = 0;
    set < pair <int, int> > Q;
    Q.insert( {0, sursa} );

    while( !Q.empty() )
    {
      pair<int, int> tmp = *(Q.begin());
      Q.erase( Q.begin() );
      u = tmp.second;

      for(int i=0; i< la[u].size(); i++)
      {
          v = la[u][i].first;
          w_uv = la[u][i].second;

          if( (d[u] + w_uv) < d[v] )
          {
            if(Q.find({d[v] , v}) != Q.end())
                Q.erase( Q.find( {d[v] , v} ) );

            d[v] = d[u] + w_uv;
            Q.insert( {d[v], v} );
          }
      }
    }

    ofstream g("dijkstra.out");
    for(int i=2; i<=n; i++)
        if(d[i] == infinit)
        g << 0 << ' ';
        else
        g << d[i] << ' ';
    g.close();

 delete []d;
}

int main()
{   int n;
    vector< pair <int, int> > *la;

    citire(n, la);
    Dijkstra(n, la, 1);

    return 0;
}