#include<cstdio>
#include<queue>
#include<utility>
using namespace std;
vector<pair< short,int> > v[50003];
FILE *f,*g;
priority_queue<pair< short,int> ,vector<pair<short,int> >,greater<pair<short,int > > > p;
int n,m,i,j,x,y,c,viz[50003],cost[50003],spa[50003];

int main ()
{f=fopen("t.in","r");
g=fopen("dijkstra.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=n;i++)
{
cost[i]=2000000000;
}

for(i=1;i<=m;i++)
{fscanf(f,"%d %d %d",&x,&y,&c);
v[x].push_back(make_pair(c,y));
spa[x]++;
}


viz[1]=1;

c=n-1;

for(i=0;i<spa[1];i++)
{                p.push(v[1][i]);
                 cost[v[1][i].second]=v[1][i].first;
                 
}

while(c)
{               if(p.empty())break;
                y=p.top().second;
                p.pop();
                if(!viz[y])
                {
                 for(i=0;i<spa[y];i++)
                 {
                  if(cost[v[y][i].second]>cost[y]+v[y][i].first)
                               {cost[v[y][i].second]=v[y][i].first+cost[y];
                               if(!viz[v[y][i].second])
                               {v[y][i].first+=cost[y];
                               p.push(v[y][i]);} 
                             
                               }
                 }
                  viz[y]=1; c--;
                 }
}
for(i=2;i<=n;i++)
if(cost[i]!=2000000000)
fprintf(g,"%d ",cost[i]);
else
fprintf(g,"0 ");
fclose(f); fclose(g);
return 0;
}