#include <iostream>
#include <fstream>
#define cmax 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a[20000][20000],n,m;
void Dijkstra()
{
    int viz[50001],d[50001];
    int i,j,ok,mini,k;
for(i=1;i<=n;i++)
    {
        d[i]=a[1][i];
        viz[i]=0;
    }
viz[1]=1;
d[1]=0;
ok=1;
while(ok)
{
    mini=cmax;
    for(i=1;i<=n;i++)
        if(viz[i]==0&&d[i]<mini)
        {
            mini=d[i];
            k=i;
        }
    if(mini!=cmax)
    {
        viz[k]=1;
        for(i=1;i<=n;i++)
            if(d[i]>d[k]+a[k][i]&&viz[i]==0)
                d[i]=d[k]+a[k][i];
    }
    else
        ok=0;
}
for(i=2;i<=n;i++)
    if(d[i]==cmax)
        fout<<"0"<<" ";
    else
        fout<<d[i]<<" ";
}

int main()
{
    int i,j,x,y,z;
fin>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        a[i][j]=cmax;
for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        a[x][y]=z;
    }
Dijkstra();
    return 0;
}