#include<fstream>
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,b[50002];

vector<int> a[50002];
vector<int> c[50002];

void read()
{
   int x,y,s;
   f>>n>>m;
   for(int i=1;i<=m;i++)
   {
       f>>x>>y>>s;
       a[x].push_back(y);
       c[x].push_back(s);
   }
}

void solve()
{
   int st,dr,i,j,x;
   vector<int>heap;
   st=dr=0;
   i=0;
   heap.push_back(1);
   while(st<=dr)
   {
       x=heap[st];
       for(i=0;i<a[x].size();i++)
       {
          if(b[a[x][i]]==0||b[a[x][i]]>b[x]+c[x][i])
          {
             b[a[x][i]]=b[x]+c[x][i];
              dr++;
             heap.push_back(a[x][i]);

          }
       }
       st++;
   }
}

void write()
{
   for(int i=2;i<=n;i++) g<<b[i]<<" ";
}

int main()
{
    read();
    solve();
    write();

    return 0;
}