//#include <fstream>
//#include <vector>
//#include <queue>
//#include <set>
//
//using namespace std;
//
//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");
//
//const int INF = 0x3f3f3f3f;
//
//int n, m;
//vector<pair<int, int>> graf[50005];
//int dist[50005];
//set<pair<int, int>> s;
//
//void dijkstra(int nod)
//{
//	dist[nod] = 0;
//	s.insert({ 0, nod });
//	while (!s.empty())
//	{
//		int cn = s.begin()->second;
//		s.erase(s.begin());
//		for (auto i : graf[cn])
//		{
//			if (dist[cn] + i.second < dist[i.first])
//			{
//				auto p = s.find({ dist[i.first], i.first });
//				if (p != s.end())
//					s.erase(p);
//				dist[i.first] = dist[cn] + i.second;
//				s.insert({ dist[i.first], i.first });
//			}
//		}
//	}
//}
//
//int main()
//{
//	fin >> n >> m;
//	int x, y, z;
//	for (int i = 1; i <= m; i++)
//	{
//		fin >> x >> y >> z;
//		graf[x].push_back({ y, z });
//		dist[i] = INF;
//	}
//	dijkstra(1);
//	for (int i = 2; i <= n; i++) 
//	{
//		if (dist[i] == INF) 
//		{
//			dist[i] = 0;
//		}
//		fout << dist[i] << ' ';
//	}
//}
#include <fstream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

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

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

int n, m;
set<pair<int, int>, cmp> graf[50005];
queue<int> q;
bool viz[50005];
int dist[50005];

void bfs(int nod)
{
    int cn;
    viz[nod] = true;
    q.push(nod);
    while (!q.empty())
    {
        cn = q.front();
        q.pop();
        for (auto nextn : graf[cn])
        {
            if (viz[nextn.first] == false)
            {
                q.push(nextn.first);
                viz[nextn.first] = true;
            }
            if (dist[nextn.first] == 0)
            {
                dist[nextn.first] = dist[cn] + nextn.second;
            }
            else
            {
                dist[nextn.first] = min(dist[cn] + nextn.second, dist[nextn.first]);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    int x, y, z;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> z;
        graf[x].insert({ y, z });
    }
    bfs(1);
    for (int i = 2; i <= n; i++)
    {
        fout << dist[i] << ' ';
    }
    return 0;
}