#include <fstream>
#include <vector>
#define oo 2000000000
#define NMax 50000
using namespace std;
int N,M;
vector <pair <int, int> >G[NMax];
int D[NMax];
int Use[NMax];
void Read()
{
    ifstream in ("dijkstra.in");
    in>>N>>M;
    for (int i=0;i<M;i++)
    {
        int A,B,C;
        in>>A>>B>>C;
        G[A].push_back(make_pair(B,C));
    }
    in.close();
}
void Solve()
{
    int Nod;
    int Cost;
    for (int i= 1;i<=N;i++)
    {
        Use[i]=0;
        D[i]=oo;
    }
    D[1]=0;
    for (int i=1;i<=N;i++)
    {
        int Min=oo;
        for (int j=1;j<=N;j++)
        {
            if (D[j]<Min&&Use[j]==0)
            {
                Min=D[j];
                Nod=j;
            }
        }
        Use[Nod]=1;
        //Relaxarea Vecinilor (imbunatatirea costului vecinilor)
        for (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 Write()
{
    ofstream out ("dijkstra.out");
    for (int i=2;i<=N;i++)
    {
        if (D[i]!=oo)
        out<<D[i]<<' ';
        else
            out<<0<<' ';
    }
}
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}