#include <cstdio>
#include <vector>
#define nmax 50000
using namespace std;

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

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()
{
    viz[1]=1; v[1]=1; k=1;
    for(x=1;x<=k;x++)
    {
        for(y=0;y<a[v[x]].size();y++)
        {
            z=a[v[x]][y];
            d=dist[v[x]][y];
            if (!viz[z]||(dmin[z]>dmin[v[x]]+d&&viz[z]))
            {
                viz[z]=1;
                dmin[z]=dmin[v[x]]+d;
                v[++k]=z;
            }
        }
    }
}

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

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