#include <fstream>

using namespace std;

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

struct qq
{
    int d,t;
    bool v;
};
qq x[50001];
int a[5001][5001],n,st,m;

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=20002;
    int q,y;
    for(int i=1;i<=m;i++)
        f>>q>>y,f>>a[q][y];
    st=1;



    x[st].v=true;
    for(int i=1;i<=n;i++)
        x[i].d=a[st][i],x[i].t=st;
    x[st].t=0;
    for(int i=1;i<n;i++)
    {
        int mini=10000,poz=-1;
        for(int j=1;j<=n;j++)
            if(!x[j].v and x[j].d<mini)
                mini=x[j].d,poz=j;
        x[poz].v=true;
        for(int j=1;j<=n;j++)
            if(!x[j].v and a[poz][j]+x[poz].d<x[j].d)
                x[j].d=a[poz][j]+x[poz].d,x[j].t=poz;

    }
    for(int i=2;i<=n;i++)
    {
        g<<x[i].d<<' ';
    }

    return 0;
}