#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

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

const int NMAX = 50005;
const int INF = 2e9;
vector<ii>G[NMAX];
int n,m;

void dijkstra(int s)
{
    vi dist(n+2,INF);
    dist[s] = 0;
    priority_queue<ii, vector<ii>, greater<ii>>pq;
    pq.push(ii(0,s));
    while(!pq.empty())
    {
        ii fr = pq.top();
        pq.pop();
        int d = fr.first, u = fr.second;
        if(d > dist[u])
            continue;
        for(auto x : G[u])
        {
            if(d + x.second < dist[x.first])
            {
                dist[x.first] = d + x.second;
                pq.push(ii(dist[x.first],x.first));
            }
        }
    }

    for(int i=2;i<=n;++i)
        fout << dist[i] << ' ';
}

int main()
{
    int i,x,y,d;
    fin >> n >> m;
    for(i=1;i<=m;++i)
    {
        fin >> x >> y >> d;
        G[x].push_back(ii(y,d));
    }

    dijkstra(1);
    return 0;
}