#include <fstream>
#define inf 10000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,a[1001][1001],t[1001],d[1001],m;
bool sel[1001];

void dijkstra()
{

int i,j,mini,k;
    for(i=1;i<=n;i++)
    {
        d[i]=inf;
        sel[i]=false;
        t[i]=0;
    }
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        mini=inf;
        for(j=1;j<=n;j++)
            if(!sel[j] && d[j]<mini)
        {
            mini=d[j];
            k=j;
        }
        sel[k]=true;
        for(j=1;j<=n;j++)
            if(!sel[j] && d[j]>d[k]+a[k][j])
        {
            d[j]=d[k]+a[k][j];
            t[j]=k;
        }
    }

}



int main()
{
    int i,x,y,c;
    f>>n>>m;
    for(i=1;i<=n; i++)
        for(int j=1;j<=n;j++)
          if(i==j)a[i][j]=0; else a[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }

dijkstra();

for(i=2;i<=n;i++)
    g<<d[i]<<" ";

}