#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#define MAXN 50005
#define INFINIT 2000000005
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair <int, int> edge;
typedef vector <edge> graf;
typedef priority_queue <edge> Heap;
graf G[MAXN + 1];
Heap H;
int D[MAXN + 1];
int main ()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G[a].pb(mp(c,b));
        }
    for (int i=1;i<=n;i++)
        D[i]=INFINIT;

    D[1]=0;
    H.push(mp(0,1));
    while (!H.empty())
        {
        edge E=H.top();
        H.pop();
        int node = E.second;
        for (graf :: iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
            if (D[node] + it -> first < D[it -> second]) {
                D[it -> second] = D[node] + it -> first;
                H.push(mp(-D[it -> second], it -> second));
            }
        }
    }

    for(int i=2;i<=n;i++)
        {
        if(D[i]==INFINIT)
            printf("0 ");
        else
            printf("%d ",D[i]);
        }
return 0;
}