#include<cstdio>
#include<queue>
#include<vector>

#define pb push_back
#define mp make_pair
#define inf (1<<30)

using namespace std;

int n,m,i,x,y,cost,ras[50004];
priority_queue< pair< int, int > > heap;
pair < int, int> X;
vector< pair < int, int > > muchie[50004];
vector< pair < int, int > >::iterator it;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d",&x,&y,&cost);
        muchie[x]. pb ( mp( y, cost) );
    }

    for (i=1; i<=n; i++)
        ras[i]=inf;

    heap.push ( mp (0, 1) );
    while (!heap.empty())
    {
        X = heap.top();
        heap.pop();
        if ( ras[X.second] != inf )continue;
        ras [X.second] = -X.first;
        for (it=muchie[X.second].begin(); it!=muchie[X.second].end(); it++)
            heap.push ( mp ( -(ras[X.second] + it->second), it->first) );
    }

    for(i=2;i<=n;i++)
    {
        if(ras[i]==inf)ras[i]=0;
        printf("%d ",ras[i]);
    }
    return 0;
}