#include <fstream>
#include <vector>

using namespace std;

const int INF=1073741824;
vector <int> G[50005];
vector <int> C[50005];
int D[50005], H[50005], P[50005], NH;
unsigned int N;

void Read ()
{
    ifstream fin ("dijkstra.in");
    int M, X, Y, Z;
    fin >> N >> M;
    for (; M>0; --M)
    {
        fin >> X >> Y >> Z;
        G[X].push_back (Y);
        C[X].push_back (Z);
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("dijkstra.out");
    unsigned int i;
    for (i=2; i<=N; ++i)
    {
        if (D[i]==INF)
            D[i]=0;
        fout << D[i] << " ";
    }
    fout << "\n";
    fout.close ();
}

void Sift (int X)
{
    int S=X<<1,Aux;
    while (S<=NH)
    {
        if ((X<<1)<NH&&D[H[S]]>D[H[(X<<1)+1]])
            ++S;
        if (D[H[S]]<D[H[X]])
        {
            Aux=P[H[X]];
            P[H[X]]=P[H[S]];
            P[H[S]]=Aux;
            Aux=H[X];
            H[X]=H[S];
            H[S]=Aux;
            X=S;
            S=X<<1;
        }
        else
        {
            return;
        }
    }
}

void Percolate (int X)
{
    int F=X>>1,Aux;
    while (F)
    {
        if (D[H[F]]>D[H[X]])
        {
            Aux=P[H[X]];
            P[H[X]]=P[H[F]];
            P[H[F]]=Aux;
            Aux=H[X];
            H[X]=H[F];
            H[F]=Aux;
            X=F;
            F=X>>1;
        }
        else
            return;
    }
}

inline void Insert (int X)
{
    H[++NH]=X;
    P[H[NH]]=NH;
    Percolate (NH);
}

void Dijkstra (int Start)
{
    unsigned int i;
    int NC;
    for (i=1; i<=N; ++i)
    {
        P[i]=-1;
        D[i]=INF;
    }
    D[Start]=0;
    P[Start]=1;
    H[++NH]=Start;
    while (NH>0)
    {
        NC=H[1];
        H[1]=H[NH--];
        P[H[1]]=1;
        Sift (1);
        for (i=0; i<G[NC].size (); ++i)
        {

            if (P[G[NC][i]]==-1)
            {
                D[G[NC][i]]=D[NC]+C[NC][i];
                Insert (G[NC][i]);
            }
            if (D[G[NC][i]]>D[NC]+C[NC][i])
            {
                D[G[NC][i]]=D[NC]+C[NC][i];
                Percolate (P[G[NC][i]]);
            }
        }
    }
}

int main()
{
    Read ();
    Dijkstra (1);
    Type ();
    return 0;
}