#include <fstream>
#define inf 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,c[5001][5001],viz[50001],d[50000],poz,v;
void cit()
{
    int i,j,k,cost;
    f>>n>>m;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            c[i][j]=inf;
    for(k=1; k<=m; ++k)
    {
        f>>i>>j>>cost;
        c[i][j]=cost;
    }
    f.close();
    v=1;
}
void init()
{
    viz[v]=1;
    int i;
    for(i=1; i<=n; ++i) d[i]=c[v][i];
}
void dijkstra()
{
    int i,j,minn;
    for(i=1; i<n; ++i)
    {
        minn=inf;
        for(j=1; j<=n; ++j)
        {
            if(viz[j]==0&&minn>d[j])
            {
                minn=d[j];
                poz=j;
            }
        }
        viz[poz]=1;
        for(j=1; j<=n; ++j)
                if(viz[j]==0&&d[j]>d[poz]+c[poz][j])
                {
                    d[j]=d[poz]+c[poz][j];
                }
    }
}
void afis()
{
    int i;
    for(i=1; i<=n; ++i) if(i!=v) g<<d[i]<<" ";
    g.close();
}
int main()
{
    cit();
    init();
    dijkstra();
    afis();
    return 0;
}