// How about a coding trick?
#include <cstdio>
#include <vector>
#include <queue>
#define DIM 50050
#define PII pair<int,int>
#define INF 2000000000
#define fi first
#define se second
using namespace std;
FILE *fin=freopen("dijkstra.in","r",stdin);
FILE *fout=freopen("dijkstra.out","w",stdout);

vector < PII > V[DIM];
vector < PII >::iterator it;
int dist[DIM], father[DIM];

class Compare_Nodes
    {
        public:
            bool operator() (int x, int y)
            {
                return dist[x] > dist[y];
            }
    };

priority_queue <int, vector<int>, Compare_Nodes> heap;
int n, m;

void Read()
{
    int x, y, cost;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m ; ++i)
    {
        scanf("%d %d %d", &x, &y, &cost);
        V[x].push_back( make_pair(y, cost) );
    }
}

void Solve()
{
    int i, vfmin;
    for(i = 2; i <= n; ++i)
        father[i] = 1, dist[i] = INF;
    father[1] = 0, dist[1] = 0; heap.push(1);

    while( !heap.empty() )
    {
        vfmin = heap.top(); heap.pop();
        for(it = V[vfmin].begin(); it != V[vfmin].end(); ++it)
            if( dist[it -> fi] > dist[vfmin] + it -> se )
            {
                dist[it -> fi] = dist[vfmin] + it -> se;
                father[it -> fi] = vfmin;
                heap.push( it -> fi );
            }
    }
    for(i = 2; i <= n; ++i)
    {
        if( dist[i] == INF )
            printf("0 ");
        else
            printf("%d ", dist[i]);
    }
}

int main()
{
    Read();
    Solve();
    return 0;
}