#include <fstream>
using namespace std;
int n,m,c,t[3][250001],coada[100001],start[50001],viz[50001],minimal[50002];
void initializare()
{
    int vmax=2000,i;
    for(i=2;i<=n;i++)
        minimal[i]=vmax;
}
void citire()
{
    int i,k=0,a,b;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        start[a]=k;
        t[2][k]=c;
    }
}
void bf()
{
    ofstream fout("dijkstra.out");
    int pr,ul,i;
    initializare();
    pr=1;ul=1;
    coada[1]=1;
    viz[1]=1;
    while(pr<=ul)
    {
        for(i=start[coada[pr]];i!=0;i=t[1][i])
        {
            if(viz[t[0][i]]==0)
            {
                ul++;
                coada[ul]=t[0][i];
                if(minimal[t[0][i]]>minimal[coada[pr]]+t[2][i])
                        minimal[t[0][i]]=minimal[coada[pr]]+t[2][i];
            }
        }
        viz[coada[pr]]=1;
        pr++;
    }
    for(i=2;i<=n;i++)
        fout<<minimal[i]<<' ';
    fout.close();
}
int main()
{
    citire();
    bf();
    return 0;
}