#include <vector>
#include <fstream>
using namespace std;

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


int minim(int* dist, int n, int* viz)
{
    int minn;
    for(int i=1; i<=n; i++)
        if(viz[i]==0)
        {
            minn=i;
            break;
        }
    for(int j=1; j<=n; j++)
    {
        if((dist[j]<dist[minn])&&(viz[j]==0))
            minn=j;
    }
    viz[minn]=1;

    return minn;
}


int main()
{
    int n,m,nod1,nod2,i,j,cost;

    in>>n>>m;

    int** a=new int*[n+1];
    for(i=0; i<=n; i++)
    {
        a[i]=new int[n+1];
        for(j=0; j<=n; j++)
            a[i][j]=0;
    }

    int dist[100003];
    int viz[100003];
    for(i=0; i<=n; i++)
    {
        dist[i]=1234567890;
        viz[i]=0;
    }

    for(i=1; i<=m; i++)
    {
        in>>nod1>>nod2>>cost;
        a[nod1][nod2]=cost;

          //  graph[nod1].push(make_pair(nod2, cost));


    }

    dist[1]=0;

    for(i=1; i<=n; i++)
    {
        int minn=minim(dist,n,viz);


        for(j=1; j<=n; j++)
            if(dist[minn]+a[minn][j]<dist[j]&&a[minn][j]!=0)
            {
                dist[j]=dist[minn]+a[minn][j];


            }


    }
    for(i=2; i<=n; i++)
       /* if(dist[i]==1234567890)
            out<<0<<" ";
        else*/

        out<<dist[i]<<" ";

    return 0;
}