#include <fstream>
#include <vector>
#define NMax 50005
#define oo 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M,D[NMax],H[NMax],Poz[NMax],NHeap;
vector < pair<int,int> > G[NMax];

void Swap(int X, int Y)
{
    swap(H[X],H[Y]);
    swap(Poz[H[X]],Poz[H[Y]]);
}
void Sift(int X)
{
    int Son=(X<<1);
    if(Son+1<=NHeap && D[H[Son+1]]<D[H[Son]])
      Son++;
    if(Son<=NHeap && D[H[Son]]<D[H[X]])
        {
            Swap(Son,X);
            Sift(Son);
        }
}
void Percolate(int X)
{
    int F=X>>1;
    if(F && D[H[X]]<D[H[F]])
        {
            Swap(X,F);
            Percolate(F);
        }
}
void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        {
            int x,y,c;
            fin>>x>>y>>c;
            G[x].push_back(make_pair(y,c));
        }
}
inline void InitDijkstra (int Start)
{
    for(int i=2;i<=N;i++)
        D[i]=oo;

    NHeap=N;

    for(int i=1;i<=NHeap;i++)
    {
        H[i]=i;
        Poz[i]=i;
    }

}
int ComputeMin()
{
    int P=H[1];
    Swap(1,NHeap);
    NHeap--;
    Sift(1);
    return P;
}
inline void Relax(int Nod,int Vecin,int Cost)
{
   if(D[Vecin]>D[Nod]+Cost)
      {
      D[Vecin]=D[Nod]+Cost;
      Percolate(Poz[Vecin]);
      }

}
void Dijkstra(int Start)
{
    InitDijkstra(Start);

    for(int i=1;i<=N;i++)
        {
            int Nod=ComputeMin();
            for(unsigned int j=0;j<G[Nod].size();j++)
                Relax(Nod,G[Nod][j].first,G[Nod][j].second);
        }
}
void Print()
{
    for(int i=2;i<=N;i++)
        {
            if(D[i]==oo)
                D[i]=0;
            fout<<D[i]<<" ";
        }
    fout<<'\n';
}
int main()
{
    Read();
    Dijkstra(1);
    Print();
    return 0;
}