#include <fstream>
#include <vector>
#define NMax 50005
#define oo 1<<30
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,Nheap,M,D[NMax],H[NMax],Poz[NMax];
vector <pair <int, int> > G[NMax];
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));
        }
}

void Swap(int x, int y)
{
    swap(H[x],H[y]);
    swap(Poz[H[x]],Poz[H[y]]);
}

void Percolate(int X)
{
    int Father=X/2;
    if(Father > 0 && D[Father]>D[X])
        {
            Swap(X,Father);
            Percolate(Father);
        }
}

void Sift(int X)
{
    int Son=2*X;

    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 Delete()
{
    Swap(1,Nheap);
    Nheap--;
    Sift(1);
}

void Dijkstra()
{
    int i,j;

    Nheap=N;

    for(i=1;i<=N;i++)
    {
        H[i]=i;
        Poz[i]=i;
    }
    for(i=2;i<=N;i++)
       D[i]=oo;

    for(i=1;i<=N;i++)
        {
            int P;
            P=H[1];
            Delete();
            for(j=0;j<G[P].size();j++)
                {
                    int Vecin=G[P][j].first,Cost=G[P][j].second;
                    if(D[Vecin]>D[P]+Cost)
                        {
                        D[Vecin]=D[P]+Cost;
                        Percolate(Poz[Vecin]);
                        }
                }
        }
}
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();
    Print();
    return 0;
}