#include<fstream>
#include<vector>
//#include<algorithm>
#include<queue>

const int maxn =50005;
const int inf=1000000;
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
int n,m;
vector<pair<int, int> >G[maxn];
int dmin[maxn];

void citire()
{f>>n>>m;
 for(int a,b,c,i=0;i<m;++i)
  {f>>a>>b>>c; G[a].push_back(make_pair(b,c));}
}
void dijks()
{ bool viz[maxn];
  queue<int>Q;
  for(int i=0;i<=maxn;i++) {dmin[i]=inf; viz[i]=false; }
     dmin[1]=0; Q.push(1); viz[1]=true;
     while(!Q.empty())
     {int nod=Q.front(); Q.pop(); viz[nod]=false;
      for(vector<pair<int, int> > ::iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
       if(dmin[nod]+it->second<dmin[it->first])
       {dmin[it->first]=dmin[nod]+it->second;
        if(!viz[it->first]) {Q.push(it->first); viz[it->first]=true;}                                        
       }
     }
}

void afisez()
{ for(int i=2;i<=n;++i) g<<(dmin[i]<inf ? dmin[i]: 0)<<" "; }
int main()
{citire();
 dijks();
 afisez();
 return 0;
}