#include <fstream>
#include <vector>

using namespace std;

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

const int oo=2000000000;
const int Nmax=50000;

int NrNoduri, NrMuchii;
int distanta[Nmax], vizitat[Nmax];


vector < pair < int, int > > listaVecini[Nmax];

void Read()
{
    fin >> NrNoduri >> NrMuchii;
    for (int i=1; i<=NrMuchii; i++)
    {
        int nod, vecin, cost;
        fin >> nod >> vecin >> cost;
        listaVecini[nod].push_back(make_pair(vecin, cost));
    }
    fin.close();
}

void Dijkstra()
{
    int nodCurent, distMinima;

    distanta[1]=0;
    for (int i=2; i<=NrNoduri; i++)
        distanta[i]=oo;

    for (int k=1; k<NrNoduri; k++)
    {
        distMinima=oo;
        for (int i=1; i<=NrNoduri; i++)
            if (distanta[i]<distMinima && vizitat[i]==0)
                distMinima=distanta[i], nodCurent=i;

        vizitat[nodCurent]=1;

        for (int i=0; i<(int)listaVecini[nodCurent].size(); i++)
        {
            int nodVecin=listaVecini[nodCurent][i].first;
            int cost=listaVecini[nodCurent][i].second;

            if (distanta[nodCurent]+cost<distanta[nodVecin])
                distanta[nodVecin]=distanta[nodCurent]+cost;
        }
    }
}

void Print()
{
    for (int i=2; i<=NrNoduri; i++)
        if (distanta[i]==oo)
            distanta[i]=0;
    for (int i=2; i<=NrNoduri; i++)
        fout << distanta[i] << " ";
    fout.close();
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}



//#include <fstream>
//#include <vector>
//using namespace std;
//
//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");
//
//const int NMax = 50000;
//const int oo = 2000000000;
//int D[NMax + 5], S[NMax + 5];
//int N,M;
//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;
//        //pair < int, int > P;
//        //P.first = y; P.second = c;
//        //G[x].push_back(P);
//        G[x].push_back(make_pair(y,c));
//    }
//}
//
//void Dijkstra()
//{
//    for(int i = 2; i <= N; ++i)
//        D[i] = oo;
//    for(int k = 1; k < N; ++k)
//    {
//        int Min = oo,Nod;
//        for(int i = 1; i <= N; ++i)
//            if(D[i] < Min && S[i] == 0)
//            {
//                Min = D[i];
//                Nod = i;
//            }
//        S[Nod] = 1;
//
//        for(int i = 0; i < (int)G[Nod].size(); ++i)
//        {
//            int Vecin = G[Nod][i].first, Cost = G[Nod][i].second;
//            D[Vecin] = min(D[Vecin],D[Nod] + Cost);
//        }
//    }
//}
//
//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;
//}