#include <fstream>
#include <vector>
#define NMax 100005
#define oo 100000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M;
vector< pair<int,int> > G[NMax];
int D[NMax],S[NMax];

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        {
            int x,y,z;
            fin>>x>>y>>z;
            pair<int, int> P;
            //P.first = y; P.second = z;
            P = make_pair(y,z);
            G[x].push_back(P);
        }
}

void Solve()
{
    for(int i=2;i<=N;i++)
        D[i]=oo;

    for(int i=1;i<=N;i++)
        {
            int Min,Nod;
            Min = oo;
            for(int j=1;j<=N;j++)
                if(D[j]<Min && !S[j])
                {
                    Min = D[j];
                    Nod = j;
                }
            S[Nod]=1;
            for(unsigned int j=0;j<G[Nod].size();j++)
                {
                    int Vecin = G[Nod][j].first, Cost = G[Nod][j].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;
    for(int i=2;i<=N;i++)
        fout<<D[i]<<" ";
}

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