#include <bits/stdc++.h>
using namespace std;

const int nmax = 50005;
int n, m, dist[nmax];
vector< pair<int,int> > g[nmax];
bool marked[nmax];

void apply_dijkstra()
{
    int i, nod;
    pair<int, int> p;
    set< pair<int,int> > s;
    s.insert(make_pair(0,1));
    dist[1] = 0;
    marked[1] = 1;
    while(!s.empty())
    {
        p=*s.begin();
        nod=p.second;
        s.erase(p);
        marked[nod] = 2;
        for(i=0; i<g[nod].size(); i++)
            if(marked[g[nod][i].second]==0)
            {
                s.insert(make_pair(dist[nod]+g[nod][i].first, g[nod][i].second));
                marked[g[nod][i].second] = 1;
                dist[g[nod][i].second] = dist[nod]+g[nod][i].first;
            }
            else if(marked[g[nod][i].second]==1 && dist[g[nod][i].second] > dist[nod]+g[nod][i].first)
            {
                s.erase(make_pair(dist[g[nod][i].second],g[nod][i].second));
                s.insert(make_pair(dist[nod]+g[nod][i].first,g[nod][i].second));
                dist[g[nod][i].second] = dist[nod]+g[nod][i].first;
            }
    }
    for(i=2; i<=n; i++)
        printf("%d ",dist[i]);
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int x, y, c;
    scanf("%d %d",&n, &m);
    for(int i=0; i<m; i++)
    {
        scanf("%d %d %d",&x, &y, &c);
        g[x].push_back(make_pair(c, y));
    }
    apply_dijkstra();
    fclose(stdin);
    fclose(stdout);
    return 0;
}