#include <cstdio>
#include <vector>
#define nmax 50001
#define infinit 2000000000
using namespace std;

vector <int> a[nmax],dist[nmax];
unsigned int v[1000000],dmin[nmax];
unsigned int n,m,x,y,i,j,k,d;

void citire()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(x=1;x<=m;x++)
    {
        scanf("%d%d%d",&i,&j,&d);
        a[i].push_back(j);
        dist[i].push_back(d);
    }
}

void dijkstra()
{
    for(x=2;x<=n;x++) dmin[x]=infinit;
    v[1]=1; k=1;
    for(x=1;x<=k;x++)
    {
        i=v[x];
        for(y=0;y<a[i].size();y++)
        {
            j=a[i][y];
            d=dist[i][y];
            if ((dmin[j]>dmin[i]+d))
            {
                dmin[j]=dmin[i]+d;
                v[++k]=j;
            }
        }
    }
}

void afisare()
{
    for(x=2;x<=n;x++)
        if (dmin[x]==infinit) printf("0\n");
        else printf("%d ",dmin[x]);
    printf("\n");
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}