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

vector <int> a[nmax],dist[nmax];
int v[1000000],dmin[nmax];
int n,m,x,y,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++)
    {
        i=v[x];
        for(y=0;y<a[i].size();y++)
        {
            j=a[i][y];
            d=dist[i][y];
            if (!viz[j]||dmin[j]>dmin[i]+d)
            {
                viz[j]=1;
                dmin[j]=dmin[i]+d;
                v[++k]=j;
            }
        }
    }
}

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

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