#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

const int INF=250000000;
const int NMAX=50005;

vector <ii> G[NMAX];
priority_queue < ii, vector <ii>, greater<ii> > pq;


int main()
{
    freopen("dijkstra.in", "r", stdin);
 //  freopen("dijkstra.out", "w", stdout);

    int n,m,u,v,w,d;

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; i++){
        scanf("%d%d%d",&u, &v, &d);
        G[u].push_back(ii(v,d));
  //      G[v].push_back(ii(u,d));
    }

    vi dist (n+1,INF);
    dist[1]=0;  // sursa = 1

    pq.push(ii(0,1));

    while(!pq.empty())
    {
        ii front=pq.top();
        pq.pop();
        d=front.first;
        u=front.second;

        if(d>dist[u])
          continue;
        for(int j=0; j < (int) G[u].size(); j++)
        {
            v=G[u][j].first;
            d=G[u][j].second;
            if(dist[u]+d < dist[v])
            {
                dist[v]=dist[u]+d;
                pq.push(ii(dist[v],v));
            }
        }
    }
    for(int i=2; i<=n; i++)
    printf("%d ", dist[i]);
    return 0;
}