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

const int maxn =50005;
const int inf=1000000;
using namespace std;
int n,m;
vector<pair<int, int> >G[maxn];
int dmin[maxn];

void citire()
{
     int i;
ifstream f("dijkstra.in");
f>>n>>m;
int a,b,c;
for(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;
int i; 
for(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()
{
     int i;
  ofstream g("dijkstra.out");
  
     for(i=2;i<=n;++i)
     g<<(dmin[i]<inf ? dmin[i]: 0)<<" ";

     
}

int main()
{
citire();
dijks();
afisez();
    
}