#include <iostream>
#include <fstream>
#define infinit 10000001

using namespace std;

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

int a[101][101],viz[101],d[101];

int main()
{int n,m,l,c,lung,i,k,pmax,j;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            a[i][j]=infinit;
    for(i=1;i<=m;i++)
    {
        f>>l>>c;
        f>>a[l][c];
    }
    viz[1]=1; d[1]=0;
    for(i=2;i<=n;i++)
    {
        d[i]=a[1][i];
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            viz[i]=1;
            for(j=1;j<=n;j++)
            {
                if(viz[j]==0&&a[i][j]+d[i]<d[j])
                {
                    d[j]=d[i]+a[i][j];
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        g<<d[i]<<" ";
    }
    return 0;
}