#include <fstream>
#define INF 999999999

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

int n,x,d[50001],t[50001],s[50001];
float C[50001][50001];

void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j)
        C[i][j]=INF;
}
void citire()
{
    int k,l,cost,m;
    fin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
    {
        fin>>k>>l>>cost;
        C[k][l]=cost;
    }
    for(int i=1;i<=n;i++)
      {
          d[i]=C[1][i];
          if(d[i]!=INF)
            t[i]=1;
      }
}
void Dijkstra()
{
    s[x]=1;
    int cmin,i,j,k,ok=1;
    for(j=1;j<=n;j++)
    {
        cmin=INF;
        for(i=1;i<=n;i++)
            if(s[i]==0)
            if(d[i]<cmin)
        {
            cmin=d[i];
            k=i;
        }
        if(cmin==INF)
            break;
        else
            s[k]=1;

        for(i=1;i<=n;i++)
            if(s[i]==0)
            if(d[k]+C[k][i]<d[i])
        {
            d[i]=d[k]+C[k][i];
            t[i]=k;

        }
    }
        for(i=2;i<=n;i++)
            fout<<d[i]<<' ';
}
int main()
{
    citire();
    Dijkstra();
    return 0;
}