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

using namespace std;

const int nmax = 50000;
const int inf = 2000000000;

struct cmp
{
    bool operator()(pair <int, int> a, pair <int, int> b)
    {
    	return a.second < b.second;
    }
};

class GRAPH
{
private:
    int n;
    vector <pair<int, int> > graph[nmax+5];
    bool viz[nmax+5];
public:
    GRAPH(int N) {n=N;memset(viz, 0, sizeof(viz));}
    void push(int x, int y, int cost)
    {
        graph[x].push_back(pair <int, int> (y, cost));
    }
    void Dijkstra(int nod, vector <int> &dist)
    {
        fill(dist.begin(), dist.end(), inf);
        priority_queue <pair <int, int>, vector <pair <int, int> >, cmp> q;
        dist[nod] = 0;
        q.push(pair <int, int> (nod, dist[nod]));
        while(!q.empty())
        {
            pair <int, int> nod = q.top();
            q.pop();
            viz[nod.first] = false;
            for(int i=0; i<graph[nod.first].size(); i++)
            {
                pair <int, int> New = graph[nod.first][i];
                if(dist[nod.first] + graph[nod.first][i].second < dist[New.first])
                {
                    dist[New.first] = dist[nod.first] + graph[nod.first][i].second;
                    if(!viz[New.first])
					{
						q.push(pair <int, int> (New.first, dist[New.first]));
						viz[New.first] = true;
					}
                }
            }
        }
        for(int i=2; i<dist.size(); i++)
            printf("%d ", dist[i]==inf ? 0 : dist[i]);
        printf("\n");
    }
};

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    vector <int> dst;
    dst.resize(n+1);
    GRAPH G(n);
    for(int i=0; i<m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G.push(a, b, c);
    }
    G.Dijkstra(1, dst);
    return 0;
}