#include<fstream>
using namespace std;

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

#define INFINIT 1000000000
#undef NULL
#define NULL 0

int c[5000][5000],dist[50001],pi[50001],n,m;

int extrage_minim(int viz[])
{
    int min1,i,j;

    min1=INFINIT;
    for(i=1;i<=n;i++)
        if(!viz[i] && dist[i]<min1)
        {
            min1=dist[i];
            j=i;
        }

    return j;
}

void dijkstra(int s)
{
    int viz[100],i,j,k,u;

    for(i=1;i<=n;i++)
    {
        dist[i]=INFINIT;
        pi[i]=NULL;//parintele
    }
    dist[s]=0;
    pi[s]=NULL;
    memset(viz,0,sizeof(viz));

    k=n;
    while(k)
    {
        u=extrage_minim(viz);
        viz[u]=1;
        k--;

        for(j=1;j<=n;j++)
            if(c[u][j] && dist[u]+c[u][j]<dist[j])
            {
                dist[j]=dist[u]+c[u][j];
                pi[j]=u;
            }
    }
}

int main()
{
    int i,j,k;

    f>>n>>m;
    while(f>>i>>j>>k) c[i][j]=k;//cost

    dijkstra(1);

    for(i=2;i<=n;i++) g<<dist[i]<<' ';

    f.close(); g.close();

    return 0;
}