#include <fstream>

using namespace std;

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

//FARA MATRICE

int n,inf=1<<15,dist[50001],k;
bool viz[50001];
int neviz;

struct da{
    int destinatie; //pana unde?
    int cost;
    da *urm;
};
da *mat[50001];

void dfs(int nod)
{
    da *q=mat[nod];
    while(q)
    {
        int i=q->destinatie;
        if(dist[nod]+q->cost<dist[i])
            dist[i]=dist[nod]+q->cost;
        q=q->urm;
    }
}

void creare_mat_adiac(int a, int b, int c/*...ost*/)
{
    da *q=new da;
    q->cost=c;
    q->destinatie=b;
    q->urm=mat[a];
    mat[a]=q;
}

int main()
{
    int m;
    in>>n>>m;
    for(int i=1 ; i<=n ; i++)
    {
        mat[i]=NULL;
        dist[i]=inf;
    }
    while(m)
    {
        int a,b,c;
        in>>a>>b>>c;
        creare_mat_adiac(a,b,c);
        if(a==1)
            dist[b]=c;
        m--;
    }
    neviz=n-1;
    viz[1]=1;
    while(neviz!=0)
    {
        /*for(int i=1 ; i<=n ; i++)
            cout<<viz[i]<<" ";
        cout<<endl;*/
        int minn=inf,imin;
        for(int i=1 ; i<=n ; i++)
            if(dist[i]<minn && viz[i]==0)
            {
                minn=dist[i];
                imin=i;
            }
        //cout<<imin<<endl;
        dfs(imin);
        viz[imin]=1;
        neviz--;
        //cout<<endl;
    }
    for(int i=2 ; i<=n ; i++)
    {
        if(dist[i]<inf)
            out<<dist[i]<<" ";
        else
            out<<0<<" ";
    }
    return 0;
}