#include<fstream>
#include<vector>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int d[50010],n,m,aux,a,b,ls,ld,c,i,j;
vector<pair<int,int> > v[50010];
int coada[1000000];
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;++i)
    d[i]=1<<30;
    ls=ld=1;
    coada[1]=1;
    while(ls<=ld)
    {
       aux=coada[ls++];
       for(unsigned int i=0;i<v[aux].size();++i)
       {
           if(d[v[aux][i].first]>d[aux]+v[aux][i].second)
           {
               d[v[aux][i].first]=d[aux]+v[aux][i].second;
               coada[++ld]=v[aux][i].first;
           }
       }
    }
    for(i=2;i<=n;++i)
    if(d[i]==1<<30)
    fout<<"0 ";
    else
    fout<<d[i]<<" ";
    return 0;
}