#include <fstream>
#include <vector>
using namespace std;
ifstream f1("dijkstra.in");
ofstream f2("dijkstra.out");
long n,m,llmax=100000;

vector<long> u(m+1,0),v(m+1,0),s(m+1,0);
vector<long> d(n+1,llmax);
void readdata()
{
   f1>>n>>m;
   for(int i=1;i<=m;i++)
   {
      f1>>u[i]>>v[i]>>s[i];
      if(u[i]==1) d[v[i]]=s[i];
   }
}

void run()
{
   bool ok;
   do
   {
      ok=false;
      for(int i=1;i<=m;i++)

         if(d[v[i]]>d[u[i]]+s[i])
            d[v[i]]=d[u[i]]+s[i], ok=true;

   } while(ok);
}

void result()
{
   for(int i=2;i<=n;i++)
      if(d[i]==llmax) f2<<0<<" "; else
         f2<<d[i]<<" ";
}

int main()
{
   readdata();
   run();
   result();
   return 0;
}