#include <iostream>
#include <fstream>
using namespace std;
ifstream r("dijkstra.in");
ofstream g("dijkstra.out");
long long n, m, i, j, k, a[3001][3001], f[3001], d[3001], aux, x, y, c;
int main()
{
    r>>n>>m;
    for(i=1;i<=m;i++)
    {
        r>>j>>k>>c;
        a[j][k]=a[k][j]=c;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==0)
                {
                    a[i][j]=999999999;
                    d[i]=999999999;
                }
    c=0;
    x=1;
    d[x]=0;
    for(i=1;i<=n;i++)
    {
        if(i!=x)
            d[i]=a[x][i];
    }
    f[x]=1;
    while(c==0)
    {
        c=1;
        for(i=1;i<=n;i++)
        {
            if(f[i]==0 && d[i]!=999999999)
            {
                c=0;
                f[i]=1;
                for(j=1;j<=n;j++)
                {
                    if(d[i]+a[i][j]<d[j])
                    {
                        d[j]=d[i]+a[i][j];
                        f[j]=0;
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=999999999)
            g<<d[i]<<" ";
        else
            g<<"-1"<<" ";
    return 0;
}