#include <fstream>
#define miel 60000
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,j,m,n,c,d[miel],t[miel],x,y;
bool used[miel];
vector <pair<int,int> >v[1000];
void dijkstra (int sursa)
{vector <pair<int,int> > ::iterator it;
    int i,minn,nod;
    d[sursa]=0;
    while (1)
    {minn=miel;
     nod=-1;
     for (i=1;i<=n;i++)
     if (!used[i]&&minn>d[i])

         {minn=d[i];nod=i;}
         if (minn==miel) break;
         used[nod]=true;
         for (it=v[nod].begin();it!=v[nod].end();it++)
         if (d[(*it).first]>d[nod]+(*it).second)
         {d[(*it).first]=d[nod]+(*it).second;
             t[(*it).first]=nod;
         }
    }
}
void afis(int i)
{
    if(t[i]) {afis(t[i]);
    g<<i<<" ";}
}
int main()
{f>>n>>m;

for (i=1;i<=m;i++)
{f>>x>>y>>c;
v[x].push_back(make_pair(y,c));
}
for (i=1;i<=n;i++) d[i]=miel;
dijkstra(1);
for (i=2;i<=n;i++) g<<d[i]<<" ";
}